Submission #1123226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123226		tfgs	Swap (BOI16_swap)	C++17	0 / 100	0 ms	320 KiB

swap

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int inf=1e18;

#ifdef LOCAL
#include "algo/debug.h"
#else
template <typename... Args>
void dummy(Args&&... args){}
#define ps dummy
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define len(x) (int)((x).size())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ai2 array<int,2>
#define ai3 array<int,3>
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }
#define pct __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
constexpr int p2(int x) { return (int)1 << x; }
constexpr int bits(int x) { return x == 0 ? 0 : 31-clz(x); } // floor(log2(x)) 
template<class T>void UNIQUE(V<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }
template<class T,class U>void erase(T& t, const U& u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }

int n;
vi a;
const int LOG=17;
V<V<V<vi>>>dp;

void merge(vi&res,const vi&a,const vi&b){
    for(int i=0,j=1;i<len(a);i+=j,j*=2){
        for(int k=i;k<min(i+j,len(a));k++)res.pb(a[k]);
        for(int k=i;k<min(i+j,len(b));k++)res.pb(b[k]);
    }
}

void solve() {
    cin>>n;
    a.rsz(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    dp.rsz(n+1,V<V<vi>>(LOG+1,V<vi>(2)));
    // needed[1][0][1]=1;
    // for(int node=1;node<=n/2;node++){
        // for(int i=0;node>>i;i++){
            // for(int j:{0,1}){
                // if(!needed[node][i][j])continue;
                // int mn=min({a[((node>>i+1)<<1)+j],a[2*node],a[2*node+1]});
                // if(mn==a[((node>>i+1)<<1)+j]){
                    // needed[2*node][0][0]=needed[2*node+1][0][1]=1;
                // }
            // }
        // }
    // }

    for(int node=n;node;node--){
        for(int i=0;node>>i;i++){
            for(int j:{0,1}){
                // if(!needed[node][i][j])continue;
                int p=((node>>(i+1))<<1)+j;
                if(2*node>n){
                    dp[node][i][j]={a[p]};
                }else if(2*node==n){
                    dp[node][i][j]={min(a[p],a[2*node]),max(a[p],a[2*node])};
                }else{
                    if(a[2*node+1]<min(a[p],a[2*node])){
                        vi tmp1,tmp2;
                        tmp1=tmp2={a[2*node+1]};
                        merge(tmp1,dp[2*node][0][0],dp[2*node+1][i+1][j]);
                        merge(tmp2,dp[2*node+1][i+1][j],dp[2*node+1][0][0]);
                        dp[node][i][j]=min(tmp1,tmp2);
                    }else{
                        if(a[p]<a[2*node]){
                            dp[node][i][j]={a[p]};
                            merge(dp[node][i][j],dp[2*node][0][0],dp[2*node+1][0][1]);
                        }else{
                            dp[node][i][j]={a[2*node]};
                            merge(dp[node][i][j],dp[2*node][i+1][j],dp[2*node+1][0][1]);
                        }
                    }
                }

            }
        }

        if(2*node<n){
            for(int i=0;2*node>>i;i++){
                for(int j:{0,1}){
                    dp[2*node][i][j].clear();
                    dp[2*node+1][i][j].clear();
                }
            }
        }
    }

    for(int i:dp[1][0][1])cout<<i<<' ';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32