https://www.acwing.com/problem/content/description/1223/

卡了好久 终于用二分过了

#include<bits/stdc++.h>
using namespace std;
const int N=2500*2500;
struct ansm{
    int s,c,d;
}ans[N];
int n;
bool cmp(struct ansm s1,struct ansm s2)
{
    if(s1.s-s2.s)return s1.s<s2.s;
    if(s1.c-s2.c)return s1.c<s2.c;
    return s1.d<s2.d;
}
int main(){
    cin>>n;
    int i=0;
    for(int c=0;c*c<=n;c++)
    for(int d=c;d*d+c*c<=n;d++)
    {
        ans[i].s=d*d+c*c;
        ans[i].c=c;
        ans[i].d=d;
     //  printf("%d %d %d\n",ans[i].s,ans[i].c,ans[i].d);
        i++;
    }
    sort(ans,ans+i,cmp);
  for(int a=0;a*a<=n;a++)
  for(int b=a;a*a+b*b<=n;b++)
  {
      int k=n-a*a-b*b;
      int l=0,r=i-1;
      while(l<r){
          int mid=(r+l)/2;
          if(ans[mid].s<k)l=mid+1;
          else r=mid;
      }
      if(ans[r].s==k&&ans[r].c>=b){
          printf("%d %d %d %d\n",a,b,ans[r].c,ans[r].d);
      return 0;}
  }
    return 0;
}