题解：P17736 [ICPC 2019 Xuzhou R] 该值太长，长度不应超过 100 个字符。

· · 题解

放个不是打表的做法。

注意到区间 [0,200] 非常小。于是考虑预处理所有答案。

枚举 a,b，你会发现因为被 [0,200] 这个区间限制住了，c 的范围是非常小的。那么双指针维护 c 的范围即可。这样复杂度是类似 5000\times 2 的平方的。

代码也是非常好理解。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define i16 short
#define u16 unsigned i16
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#ifdef int
#define i32 signed
#define u32 unsigned
#define inf (int)(1e18)
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#else
#define ll long long
#define ull unsigned ll
#define inf (int)(1e9)
#define infl (int)(1e18)
#define popc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
#define popcl(x) __builtin_popcountll(x)
#define ctzl(x) __builtin_ctzll(x)
#define clzl(x) __builtin_clzll(x)
#define pll pair<ll,ll>
#endif
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define push emplace
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
const int N=1e6+10,mod=1e9+7;
int cb[N];
pair<int,pii>ans[N];
void solve()
{
    int x;
    cin>>x;
    if(x==0) cout<<0<<' '<<0<<' '<<0<<'\n';
    else if(ans[x]==pair<int,pii>{0,pii{0,0}}) cout<<"impossible\n";
    else cout<<ans[x].fi<<' '<<ans[x].se.fi<<' '<<ans[x].se.se<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    for(int a=-5000;a<=5000;a++) cb[a+5000]=a*a*a;
    for(int a=5000;a>=-5000;a--)
    {
        int lp=-5000,rp=lp;
        for(int b=5000;b>=a;b--)
        {
            int l=-cb[a+5000]-cb[b+5000],r=l+200;
            while(lp!=5001&&cb[lp+5000]<l) lp++;
            if(lp==5001) break;
            while(rp!=5001&&cb[rp+5000]<=r) rp++;
            for(int i=lp;i!=rp;i++) ans[cb[a+5000]+cb[b+5000]+cb[i+5000]]={a,{b,i}};
        }
    }
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

::: 你以为这就完了？我们可是要抢最优解的！

首先不妨钦定三个数的大小关系，这样可以减少不少常数。

又会发现，a,b,c 较大的时候 c 肯定是最多只有一种的，因此暴力处理 |a|,|b|,|c|\le 10 的情况，剩下的情况双指针就只需要一个指针了。

又会发现预处理值域只需要到 4280，我不知道这为什么是对的但这就是对的。

最慢点 33ms，应该是非打表并列最优解。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define i16 short
#define u16 unsigned i16
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#ifdef int
#define i32 signed
#define u32 unsigned
#define inf (int)(1e18)
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#else
#define ll long long
#define ull unsigned ll
#define inf (int)(1e9)
#define infl (int)(1e18)
#define popc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
#define popcl(x) __builtin_popcountll(x)
#define ctzl(x) __builtin_ctzll(x)
#define clzl(x) __builtin_clzll(x)
#define pll pair<ll,ll>
#endif
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define push emplace
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
const int N=1e6+10,mod=1e9+7;
int cb[N];
pair<int,pii>ans[N];
void solve()
{
    int x;
    cin>>x;
    if(x==0) cout<<0<<' '<<0<<' '<<0<<'\n';
    else if(ans[x]==pair<int,pii>{0,pii{0,0}}) cout<<"impossible\n";
    else cout<<ans[x].fi<<' '<<ans[x].se.fi<<' '<<ans[x].se.se<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    for(int a=-4280;a<=4280;a++) cb[a+4280]=a*a*a;
    for(int a=-10;a<=10;a++) for(int b=a;b<=10;b++) for(int c=b;c<=10;c++) if(cb[a+4280]+cb[b+4280]+cb[c+4280]>=0&&cb[a+4280]+cb[b+4280]+cb[c+4280]<=200) ans[cb[a+4280]+cb[b+4280]+cb[c+4280]]={a,{b,c}};
    for(int a=4280;a>=6;a--)
    {
        int lp=-4280;
        for(int b=a;b>=-4280;b--)
        {
            int l=-cb[a+4280]-cb[b+4280],r=l+200;
            while(lp!=b+1&&cb[lp+4280]<l) lp++;
            if(lp==b+1) break;
            if(cb[lp+4280]<=r) ans[cb[a+4280]+cb[b+4280]+cb[lp+4280]]={a,{b,lp}};
        }
    }
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

:::