第七届蓝桥杯省赛C++A/B组 四平方和

#include<bits/stdc++.h>
using namespace std;
const int N=5*1e6+10;
struct sum{
    int c,d,s;
    bool operator<(const sum &W)const{
        if(s!=W.s) return s<W.s;
        if(c!=W.c) return c<W.c;
        return d<W.d;
    }
}Sum[N];
int main(){
    int n;scanf("%d",&n);
    int idx=0;
    for(int i=0;i*i<=n;i++){
        for(int j=i;j*j+i*i<=n;j++){
            Sum[idx++]={i,j,i*i+j*j};
        }
    }
    sort(Sum,Sum+idx);
    for(int i=0;i*i<=n;i++){
        for(int j=i;j*j+i*i<=n;j++){
            int l=0,r=idx;
            while(l<r){
                int mid=l+r>>1;
                int x=Sum[mid].c,y=Sum[mid].d;
                if(x*x+y*y+i*i+j*j>=n) r=mid;
                else l=mid+1;
            }
            int x=Sum[l].c,y=Sum[l].d;
            if(x*x+y*y+i*i+j*j==n){
                printf("%d %d %d %d\n",i,j,x,y);
                return 0;
            }
        }
    }
    return 0;
}