【題解】Codeforces 1500A. Going Home

#include <bits/stdc++.h>
using namespace std;
 
int n, a[200005];
vector <pair<int, int> > v;
 
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        v.push_back({a[i], i});
    }
    if (n <= 3500){
        map <int, vector<pair<int, int> > > mp;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (i == j || a[i] > a[j] || (a[i] == a[j] && i > j)) continue;
                int tmp = a[j]-a[i];
                if (mp.count(tmp)){
                    for (auto [x, y]:mp[tmp]){
                        if (i != x && i != y && j != x && j != y){
                            cout << "YES\n";
                            cout << x << " " << j << " " << i << " " << y << "\n";
                            return 0;
                        }
                    }
                }
                mp[tmp].push_back({i, j});
            }
        }
    }
    else{
        sort(v.begin(), v.end());
        map <int, pair<int, int> > mp;
        for (int i = 1; i < n; i++){
            int tmp = v[i].first-v[i-1].first;
            if (mp.count(tmp)){
                if (mp[tmp].second == v[i-1].second) continue;
                else{
                    cout << "YES\n";
                    cout << mp[tmp].first << " " << v[i].second << " ";
                    cout << mp[tmp].second << " " << v[i-1].second << "\n";
                    return 0;
                }
            }
            else mp[tmp] = {v[i-1].second, v[i].second};
        }
    }
    cout << "NO\n";
}