思路

对于数据要求是5e6，四个数的上限都是$\sqrt{n}\approx2236$，因而暴力枚举最多只能枚举两个位上的数，故考虑空间换时间的做法：abcd分别表示升序的四个数，第一步先枚举c(0~$\sqrt{n}$)，后枚举d(c~$\sqrt{n-c^2}$)；然后把每一组(c,d)的平方和的值存下；第二步枚举a(0~$\sqrt{n}$)，b(a~$\sqrt{n-a^2}$)，然后对于每一组(a,b)，计算a、b平方和与n的差距$t=n-a^2-b^2$，判断是否在先前记录过的(c,d)的平方和中出现过$\Rightarrow$两种做法：哈希（$log(1)$）/二分（log(n)）

注意

1.为保证abcd升序排列，a、b与c、d在枚举时两组已确保组内升序，对于abcd整体升序，即对每一个t以及找到的满足要求的(c,d)组，要求是升序排列。为此可以定义一个结构体存储$c^2+d^2、c、d$的值，然后重载小于号并按$c^2+d^2、c、d$的顺序来进行比较
2.结构体的索引上限设置为2500010，即约2.5e6，以确保能存储所有可能的三元组（$c^2+d^2，c，d$）因为c、d双重循环的时间复杂度约为$\dfrac{\sqrt{n}*\sqrt{n}}{2}=\dfrac{5e6}{2}=2.5e6$（c从0-n，d从c到$\sqrt{n-c^2}$）
3.使用第二个二分模版而不是第一个，因为r=mid找的是第一个满足条件的，l=mid找的是最后一个满足条件的

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2500010;
int n, m;

struct Sum
{
    int s;
    int c;
    int d;
    bool operator<(const Sum &t) const
    {
        if (s != t.s)
            return s < t.s;
        if (c != t.c)
            return c < t.c;
        return d < t.d;
    }
} sum[N];

int main()
{
    scanf("%d", &n);
    for (int c = 0; c * c <= n; c++)
        for (int d = c; c * c + d * d <= n; d++)
            sum[m++] = {c * c + d * d, c, d};
    sort(sum, sum + m);
    for (int a = 0; a * a <= n; a++)
        for (int b = a; a * a + b * b <= n; b++)
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t)
                    r = mid;
                else
                    l = mid + 1;
                if (sum[l].s == t)
                {
                    printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                    return 0;
                }
            }
        }
    return 0;
}