AcWing 1221. 四平方和 (哈希 or 二分 ）

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=5e6+10;
int n,cnt;
struct node{
    int val,x,y;
    bool operator<(const node& a)const {
        if(val==a.val)return x<a.x;
        return val<a.val;
    }
}p[N];
ostream & operator<<(ostream & os,node &a){
    cout<<a.val<<" "<<a.x<<" "<<a.y<<endl;
}
int main(){
    cin>>n;
    for(int c=0;c*c<=n;c++){
        for(int d=c;c*c+d*d<=n;d++){
            p[cnt++]={c*c+d*d,c,d};
        }
    }
    
    sort(p,p+cnt);
    for(int a=0;a*a<=n;a++){
        for(int b=a;b*b+a*a<=n;b++){
            int test=n-a*a-b*b;
            //cout<<test<<endl;
            int l=0,r=cnt-1;
            while(l<r){
                int mid=l+r+1>>1;
                if(p[mid].val<=test){
                    l=mid;
                }
                else r=mid-1;
            }
            if(p[l].val==test){
                while(p[l].val==test)l--;
                l++;
                printf("%d %d %d %d\n",a,b,p[l].x,p[l].y);
                exit(0);
            }
        }
    }
}