P8635 [Lanqiao Cup 2016 NOI Qualifier AB] Four Squares Sum

The Four Squares Theorem, also called Lagrange's theorem, states: Every positive integer can be written as the sum of squares of at most $4$ positive integers. If we also allow $0$, then it can be written as the sum of squares of exactly $4$ numbers. For example: $5=0^2+0^2+1^2+2^2$. $7=1^2+1^2+1^2+2^2$. For a given positive integer, there may be multiple representations as a sum of squares. You need to sort the four numbers so that $0 \le a \le b \le c \le d$. Then sort all possible representations in ascending order using $a,b,c,d$ as a combined key, and finally output the first representation.

The input is a positive integer $N(N

Output $4$ non-negative integers in increasing order, separated by spaces.

Time limit: 3 seconds, 256M. Lanqiao Cup 2016, the 7th provincial contest. Lanqiao Cup 2016 provincial contest, Group A Problem H (Group B Problem H). Translated by ChatGPT 5