Trường hợp 1: Dãy ~a~ tồn tại ~4~ giá trị bằng nhau hoặc ~2~ cặp giá trị bằng nhau thì ta luôn tìm được bộ ~4~ số thỏa mãn.

Trường hợp 2: Dãy ~a~ có tối đa một cặp giá trị bằng nhau

• ~a_i \leq 2 \cdot 10^6~ suy ra ~a_i + a_j \leq 4 \cdot 10^6~.

• Ta chỉ cần duyệt khoảng ~3000~ số đầu tiên vì ~3000~ số tạo ra ~3000 \cdot (3000 - 1) / 2 > 4 \cdot 10^6~ cặp số. Theo nguyên lí Dirichlet ta có thể chứng minh được trong 3000 số nguyên phân biệt ~a_i \leq 2 \cdot 10^6~, luôn tồn tại ít nhất 2 cặp số có tổng bằng nhau.

Vậy ta có thể dễ dàng giải bài toán trong độ phức tạp ~O(\min(n, 3000)^2)~.

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+1;
int n,a[N];
int c[10*N];
pair<int,int> p[20*N];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int c2=-1;
    for(int i=1;i<=n;i++)
    {
        c[a[i]]++;
        if(c[a[i]]==4)
        {
            for(int j=1;j<=i;j++) if(a[j]==a[i]) cout<<j<<" ";
            return 0;
        }
        if(c[a[i]]==2)
        {
            if(c2==-1) c2=a[i];
            else
            {
                int d0=-1,d1=-1,e0=-1,e1=-1;
                for(int j=1;j<=n;j++)
                {
                    if(a[j]==c2)
                    {
                        if(d0==-1) d0=j;
                        else if(d1==-1) d1=j;
                    }
                    else if(a[j]==a[i])
                    {
                        if(e0==-1) e0=j;
                        else if(e1==-1) e1=j;
                    }
                }
                cout<<d0<<" "<<e0<<" "<<d1<<" "<<e1;
                return 0;
            }
        }
    }
    for(int i=1;i<=min(n,3000);i++)
        for(int j=i+1;j<=min(n,3000);j++)
    {
        int x=a[i]+a[j];
        if(p[x].f and p[x].s and p[x].f!=i and p[x].s!=i and p[x].f!=j and p[x].s!=j)
        {
            cout<<p[x].f<<" "<<p[x].s<<" "<<i<<" "<<j;
            return 0;
        }
        p[x]={i,j};
    }
    cout<<-1;
}