题解：P12402 [COI 2025] 贪腐 / Korupcija

· · 题解

怎么没人做，写个题解好了。 upd:发完题解一下就有一堆人做了

首先打表发现，只要 b_i 全是偶数就能构造。注意 n=1 要特判。

考虑归纳构造。考虑去掉 b_{n-1}。

我们可以做若干次 b_{n-1} \to b_{n-1} - 2,b_i \to b_i+2 (i<n-1) 的操作，直到 b_{n-1} 变为 0。

如果此时 b_i 能够做到全是 4 的倍数，把 b_i\to \dfrac{b_i}{2} 递归构造一个方案，然后对于这个子方案，每个 pair (x,y) 可以变成 (x,y),(x+2^{n-1},y+2^{n-1})，也可以变成 (x,x+2^{n-1}),(y,y+2^{n-1})。把一个第一种变成第二种就可以使得 n-1 多 2 个，i 减少 2 个。

那么能否做到呢？事实上只要保证能把前面每个 \frac{b_i}{2} 是奇数的必须要 +2，也就是 b_{n-1} 如果足够大就满足了。

将 b_i 从小到大排序，此时 b_{n-1} 是最大的，且至少有 \frac{2^{n-1}}{n} 级别。对于 n 大的情况就一定能归纳，不能归纳的情况最大的是 2,6,6,6,6,6，暴力找方案即可。

int n;
pii b[maxn];
bool vis[maxn];

namespace br{

int n;
int z[maxn],nd[maxn],lim;
bool ok=0;
vector<vector<pii>>qwq;
void dfs(int u){
    if(ok) return;
    while(vis[u])++u;
    if(u==(1<<n)){
        bool ook=1;
        For(i,0,n-1) ook&=(z[i]==nd[i]);
        if(ook) ok=1;
//      For(i,0,n-1) cout<<z[i]<<" "; cout<<"\n";
        return;
    }
    For(i,0,n-1){
        int v=(u^(1<<i));
        if(!vis[v]){
            vis[u]=vis[v]=1;
            ++z[i]; qwq[i].pb({u,v});
            dfs(u+1);
            if(ok) return;
            vis[u]=vis[v]=0;
            --z[i]; qwq[i].pop_back();
        }
    }
}

vector<vector<pii>>brute(vi o){
    vi bs1={2,6,6,6,6,6};
    n=o.size();
    qwq.resize(n);
    if(o==bs1){
        vector<pii>res= {{0,1},{32,33},{16,18},{48,50},{8,10},{40,42},{24,26},{56,58},{2,6},{34,38},{17,21},{49,53},{9,13},{41,45},{4,12},{36,44},{20,28},{52,60},{22,30},{54,62},{3,19},{35,51},{11,27},{43,59},{7,23},{39,55},{14,46},{25,57},{5,37},{29,61},{15,47},{31,63}};
        for(auto [x,y]:res){
            int k=__lg(x^y);
            qwq[k].pb({x,y});
        }
        return qwq;
    }
    For(i,0,n-1) nd[i]=o[i];
    ok=0;
    dfs(0);
//  cout<<"??? "<<ok<<endl;
    return qwq;
}

}

vector<vector<pii>>solve(vector<int>o){
    int n=o.size();
//  cout<<"solve "<<n<<"\n";
//  for(int x:o)cout<<x<<" "; cout<<" \n";
    if(n==1) return br::brute(o);
    vi o2=o;
    int x=o2.back(); o2.pop_back();
    vi dl(n-1);
    For(i,0,n-2) if(o2[i]/2%2==1) o2[i]+=2,dl[i]++,x-=2;
    if(x<0) return br::brute(o);
    o2.back()+=x,dl.back()+=x/2;
    For(i,0,n-2) o2[i]/=2;
    vector<vector<pii>>res(n),pre=solve(o2);
    For(i,0,n-2){
        For(j,0,o2[i]-1){
            if(dl[i]){
                res[n-1].pb({pre[i][j].fi,pre[i][j].fi|(1<<(n-1))});
                res[n-1].pb({pre[i][j].se,pre[i][j].se|(1<<(n-1))});
                --dl[i];
            } 
            else{
                res[i].pb(pre[i][j]);
                res[i].pb({pre[i][j].fi|(1<<(n-1)),pre[i][j].se|(1<<(n-1))});
            }
        }
    }
    return res;
}

void work()
{
    n=read();
    For(i,0,n-1)b[i].fi=read(),b[i].se=i;
    if(n==1){
        puts("0 1");
        exit(0);
    }
    For(i,0,n-1)if(b[i].fi%2==0); else puts("-1"),exit(0);
    sort(b,b+n);

    vi o;
    For(i,0,n-1) o.pb(b[i].fi);
    vector<vector<pii>>res=solve(o);

    auto trs=[&](int x){
        int y=0;
        For(i,0,n-1)if(x>>i&1)y|=(1<<b[i].se);
        return y;
    };
    for(auto it:res) for(auto [x,y]:it) cout<<trs(x)<<" "<<trs(y)<<endl;
//  dfs(0);
//  for(auto it:s){
//      for(int x:it)cout<<x<<" ";
//      cout<<"\n";
//  }
}

signed main()
{
    int T=1;
    while(T--)work();
    return 0;
}
/*

*/