Haidora and sticks (Editorial)

Solution

It's optimal to construct with the Triangular Construction i.e. we keep summing numbers from $1$ to $m$ until sum S \le x , We know that the sum of first $m$ integers is :

Notice that $T(m)$ is increasing ! , thus we can binary search on maximum $m$ such that T(m) \le m , With bounds l=1 and r=2 \cdot 10^9 which will be safe , since T(2 \cdot 10^9) > 2 \cdot 10^{18} which is sufficient in order to solve the problem and also fits the long 'long long' range for C++.

Once we get $m$ , we come to find the maximum stick length , the answer in this case will be the maximum of $m$ — the largest integer that we used in the triangular construction and the maximum of left integers , Fromally

Complexity \mathcal{O}(\log(2\cdot 10^9) \cdot t).

def T(n):return (n*(n+1))//2

def solve():
    n=int(input())
    l,r=1,2*10**9
    while(l<=r):
        m=(l+r)//2
        if(T(m)<n<T(m+1)):
            ans=m+1
            break
        if(T(m)==n):
            ans=m
            break
        if(T(m)<n):
            l=m+1
        if(T(m)>n):
            r=m-1
    if(T(ans)>n):ans-=1
    print(ans,max(ans,n-T(ans-1)))

for _ in range(int(input())):
    solve()