二分

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e7 + 5;

struct Node{
    int s, c, d;
    bool operator < (const Node& other) const{
        if(s != other.s) return s < other.s;
        if(c != other.c) return c < other.c;
        return d < other.d;
    }
}nodes[N];
int n;


int main(){
    cin >> n;
    int cnt = 0;
    for(int c = 0; c * c <= n; c ++ ){
        for(int d = c; c * c + d * d <= n; d ++ ){
            nodes[cnt ++ ] = {c * c + d * d, c, d};
        }
    }
    sort(nodes, nodes + cnt);


    int a, b;
    for(a = 0; a * a <= n; a ++ ){
        for(b = a; a * a + b * b <= n; b ++ ){
            int x = n - a * a - b * b;
            int l = 0, r = cnt - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(nodes[mid].s >= x) r = mid; // 左边第一个
                else l = mid + 1;
            }
            if(nodes[l].s == x) {
                printf("%d %d %d %d", a, b, nodes[l].c, nodes[l].d);
                return 0;
            }
        }
    }
    return 0;
}