[CF1500A] Going Home
Description
给定长度为 (n) 的序列 (a)，求出任意一组 (x,y,z,w) 满足：
- (x,y,z,w) 互不相同；
- (a_x+a_y=a_z+a_w)；
如果有解，输出一行 YES 后输出任意一组解；否则输出一行 NO。
(4leq nleq 2 imes10^5;1leq a_ileq 2.5 imes10^6;)
Solution
这是一个过于复杂的做法
无非四种形式，AAAA,AABB,AABC,ABCD
对前三种，随便暴力即可
对第四种，根号分治一下，对稀疏情况枚举数字，对稠密情况枚举差
正经做法是，直接暴力 (O(n^2)) 枚举，记录每一对的 sum，遇到相同的直接退出，根据鸽巢原理，显然只要 (O(n)) 次后就一定会撞到一样的
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2500005;
int n, a[N];
struct pii
{
int first;
int second;
bool operator<(const pii &b) const
{
return first < b.first;
}
bool operator==(const pii &b) const
{
return first == b.first;
}
};
pii aa[N];
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
map<int, int> mp;
for (int i = 1; i <= n; i++)
mp[a[i]]++;
vector<int> v4, v2;
for (auto [x, y] : mp)
{
if (y >= 4)
v4.push_back(x);
if (y >= 2)
v2.push_back(x);
}
if (v4.size())
{
int val = v4[0];
vector<int> ans;
for (int i = 1; i <= n; i++)
if (a[i] == val)
ans.push_back(i);
cout << "YES" << endl;
cout << ans[0] << " " << ans[1] << " " << ans[2] << " " << ans[3] << endl;
}
else if (v2.size() >= 2)
{
vector<int> ans1, ans2;
{
int val = v2[0];
for (int i = 1; i <= n; i++)
if (a[i] == val)
ans1.push_back(i);
}
{
int val = v2[1];
for (int i = 1; i <= n; i++)
if (a[i] == val)
ans2.push_back(i);
}
cout << "YES" << endl;
cout << ans1[0] << " " << ans2[0] << " " << ans1[1] << " " << ans2[1] << endl;
}
else
{
int flag = 0, vp = 0, vq = 0;
if (v2.size())
{
int val = v2[0];
set<int> s;
for (int i = 1; i <= n; i++)
if (a[i] != val)
s.insert(a[i]);
for (int i = 1; i <= n; i++)
if (a[i] != val)
{
if (s.find(2 * val - a[i]) != s.end())
{
flag = 1;
vp = val;
vq = a[i];
}
}
}
if (flag == 1)
{
vector<int> ans;
{
int val = v2[0];
for (int i = 1; i <= n; i++)
if (a[i] == val)
ans.push_back(i);
}
ans.resize(2);
for (int i = 1; i <= n; i++)
if (a[i] == vq)
ans.push_back(i);
for (int i = 1; i <= n; i++)
if (a[i] == 2 * vp - vq)
ans.push_back(i);
cout << "YES" << endl;
cout << ans[0] << " " << ans[1] << " " << ans[2] << " " << ans[3] << endl;
}
else
{
for (int i = 1; i <= n; i++)
aa[i] = {a[i], i};
sort(aa + 1, aa + n + 1);
n = unique(aa + 1, aa + n + 1) - aa - 1;
for (int i = 1; i <= n; i++)
a[i] = aa[i].first;
if (n < 20000)
{
vector<int> b(N * 2);
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
b[a[i] + a[j]]++;
if (*max_element(b.begin(), b.end()) > 1)
{
int tmp = max_element(b.begin(), b.end()) - b.begin();
vector<int> ans;
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (a[i] + a[j] == tmp)
ans.push_back(i), ans.push_back(j);
cout << "YES" << endl;
cout << aa[ans[0]].second << " " << aa[ans[1]].second << " " << aa[ans[2]].second << " " << aa[ans[3]].second << endl;
}
else
{
cout << "NO" << endl;
}
}
else
{
vector<int> b(N * 2);
for (int i = 1; i <= n; i++)
b[a[i]] = i;
for (int d = 1; d <= 130; d++)
{
int a00 = 0, a01 = 0, a10 = 0, a11 = 0;
for (int i = 1; i < N; i++)
if (b[i] && b[i + d])
{
if (a00 == 0)
{
a00 = b[i];
a01 = b[i + d];
}
else
{
if (a00 != b[i] && a00 != b[i + d] && a01 != b[i] && a01 != b[i + d])
{
a10 = b[i];
a11 = b[i + d];
break;
}
}
}
if (a10)
{
cout << "YES" << endl;
cout << aa[a00].second << " " << aa[a11].second << " " << aa[a01].second << " " << aa[a10].second << endl;
return 0;
}
// if (vec.size() > 1)
// {
// cout << "YES" << endl;
// cout << aa[vec[0].first].second << " " << aa[vec[1].second].second << " " << aa[vec[1].first].second << " " << aa[vec[0].second].second << endl;
// return 0;
// }
}
cout << "NO" << endl;
}
}
}
}