该值太长，长度不应超过 100 个字符。

· · 题解

给出一个 \mathcal{O}(V^2+T) 的非打表做法，其中 V=5000。申请卡掉打表做法然后升青。

考虑一个很显然的做法：枚举 a,b，拿 cbrt 算出 c，但是这样子是 \mathcal{O}(V^2T) 再加上一个 cbrt 的大常数，过不去。

怎么办？我会打表！ 打表太邪恶了，考虑优化。

首先你意识到把 V^2 去掉很困难，而 V^2T=2.5\times 10^8，直接爆了啊，所以考虑把所有答案预处理出来。那不和打表本质相同吗。

你发现当 a,b,c 同时有正数和负数时，柿子可以转化成 a^3+b^3-c^3=x 或者 c^3-a^3-b^3=x 的形式，而枚举 b 时，s=a^3+b^3 是单调递增的。这启发我们拿一个指针维护不超过 s 的最大立方 k^3。

得到这个之后怎么办呢，你发现 0\le x \le 200，从这个指针向两侧扩展直到 |s-k^3|>200，记录答案即可。显然这个扩展是常数次的。

:::info[更具体的，] 若 0\le s-k^3\le200，则

a^3+b^3+(-k)^3=s-k^3

有答案 (a,b,-k)。

若 0\le k^3-s\le200，则

(-a)^3+(-b)^3+k^3=k^3-s
有答案 (-a,-b,k)。

那 a,b,c\ge 0 怎么办呢？这种情况下 a,b,c \le 5，直接暴力即可。

轻松拿下非打表最优解。那不还是被打表打爆了吗。

:::success[Code]

#include<bits/stdc++.h>
#define int long long
#define For(a,b,c) for(int a=(int)b;a<=(int)(c);a++)
using namespace std;
constexpr int N=5e3+5,MOD=998244353;
int pw[N],ans[205][3],vis[205],x;
void f(int x,int a,int b,int c){
    if(x<0||x>200) return;
    vis[x]=1,ans[x][0]=a,ans[x][1]=b,ans[x][2]=c;
}
signed main(){
    For(i,0,5000)
        pw[i]=i*i*i;
    For(a,0,5)
        For(b,0,5)
            For(c,0,5)
                f(pw[a]+pw[b]+pw[c],a,b,c);
    For(a,0,5000){
        int c=a;
        For(b,0,a){
            int s=pw[a]+pw[b];
            while(c<5000&&pw[c+1]<=s) c++;
            if(c==5000&&s-pw[c]>200) break;
            for(int k=c;k>=0&&s-pw[k]<=200;k--)
                f(s-pw[k],a,b,-k);
            for(int k=c+1;k<=5000&&pw[k]-s<=200;k++)
                f(pw[k]-s,-a,-b,k);
        }
    }
    int t;
    cin>>t;
    while(t--){
        cin>>x;
        if(vis[x])
            cout<<ans[x][0]<<' '<<ans[x][1]<<' '<<ans[x][2]<<'\n';
        else
            cout<<"impossible\n";
    }
    return 0;
}

:::