AcWing 1221.四平方和 (二分)
作者:
冰冷酒
,
2022-02-21 20:00:21
,
所有人可见
,
阅读 168
#include <bits/stdc++.h> // 先预处理两个,再用二分处理两个,比较好用的二分优化
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1000010;
struct node
{
int a, b;
int sum;
bool operator < (const node & w) const
{
if (sum != w.sum)
return sum < w.sum;
return a < w.a;
}
}s[N];
int idx;
struct Node
{
int a, b, c, d;
bool operator < (const Node & w) const
{
if (a != w.a)
return a < w.a;
else if (b != w.b)
return b < w.b;
else if (c != w.c)
return c < w.c;
return d < w.d;
}
}ans[N];
int idxx;
int aa[5];
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i * i <= n; i ++)
for (int j = i; i * i + j * j <= n; j ++)
{
s[++ idx] = {i, j, i * i + j * j};
}
sort(s + 1, s + idx + 1);
for (int i = 0; i * i <= n; i ++)
for (int j = i; j * j + i * i <= n; j ++)
{
int cnt = n - i * i - j * j;
int l = 1, r = idx;
while (l < r)
{
int mid = l + r >> 1;
if (s[mid].sum >= cnt) r = mid;
else l = mid + 1;
}
if (s[l].sum == cnt)
{
aa[1] = i, aa[2] = j, aa[3] = s[l].a, aa[4] = s[l].b;
sort(aa + 1, aa + 5);
ans[++ idxx] = {aa[1], aa[2], aa[3], aa[4]};
}
}
sort(ans + 1, ans + idxx + 1);
cout << ans[1].a << ' ' << ans[1].b << ' ' << ans[1].c << ' ' << ans[1].d << endl;
return 0;
}