CF 1500A Going Home

题目描述

http://codeforces.com/contest/1500/problem/A

简要题意：给定 $n$ 个整数 $a_i$，求是否存在四个不同的位置 $x,y,z,w$ 满足 $a_x+a_y=a_z+a_w$

$n\le 2\times 10^6,a_i\le 2.5\times 10^6$

Solution

我们考虑总权值范围只有 $5\times 10^6$，所以我们只需要暴力枚举即可

#include <iostream>
#define maxn 200010
#define maxm 5000010
using namespace std;

int n, a[maxn];

pair<int, int> p[maxm];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) 
        for (int j = i + 1; j <= n; ++j) {
            int v = a[i] + a[j];
            if (p[v] == make_pair(0, 0)) p[v] = { i, j }; 
            else if (p[v].first != i && p[v].second != i && p[v].first != j && p[v].second != j) {
                cout << "YES\n"; 
                cout << p[v].first << " " << p[v].second << " "; 
                cout << i << " " << j;
                return 0; 
            }
        }
    cout << "NO\n"; 
    return 0;
}