普及组签到题求条

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define ll long long
#define re register
#define for_(i,a,b) for(int i=(a);i<=(b);i++)
#define _for(i,a,b) for(int i=(a);i>=(b);i--)
#define lc(q) ((q)<<1)
#define rc(q) ((q)<<1|1)
#define mid(l,r) (((l)+(r))>>1)

using namespace std;

namespace IO {
    inline int read() {
        char ch = getchar();
        int s = 0, f = 1;
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * f;
    }

    inline void write(int x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }

    inline void writeln(int x) {
        write(x);
        putchar('\n');
    }
}

using namespace IO;

const int N=(1<<17)+5;
const int INF=LLONG_MAX;

int a[N],rev[N],f[N],q[N],cnt,n,m,i,j,k,w,t;

inline int check(int N,int K){
    if(N<<1>=n){
        if(a[N<<1]<K) 
            f[N] = INF;
        else {
            if(a[(N<<1)+1]<K) 
                f[N] = a[N];
            else 
                f[N] = 0;
        }
    } 
    else {
        check(N<<1,K);
        check((N<<1)+1,K);
    }
    int ans = f[N<<1]+min(a[N],f[(N<<1)+1]);
    f[N]=min(INF,ans);
    return f[N];
}

inline void dfs(int N){
    int L=1,R=n,M;
    while(L<R){
        M=L+R+1>>1;
        if(check(N,M)<=w)
            L=M;
        else 
            R=M-1;
    }
    check(N,L);
    L=rev[L];w-=f[N];
    q[++cnt]=a[L];
    q[++cnt]=a[L^1];
    for(int I=L>>1;I!=N;I>>=1){
        if(I&1)
            w+=f[I^1];
        else if(f[I^1]<=a[I>>1])
            w+=f[I^1];
        else if(w>=f[I^1]-a[I>>1])
            w+=a[I>>1];
        dfs(I^1);
    }
}

signed main(){
    t=read();
    while(t--){
        m=read(),w=read();
        n=1<<m;cnt=0;
        for_(i,1,2*n-1)
            a[i]=read();
        for_(i,n,2*n-1)
            rev[a[i]]=i;
        dfs(1);
        for_(i,1,n)
            writeln(q[i]);
    }
}