Submission #538911

#	Time	Username	Problem	Language	Result	Execution time	Memory
538911		qwerasdfzxcl	Swap (BOI16_swap)	C++14	0 / 100	110 ms	188408 KiB

swap

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> dp[200200][20][2];
int a[400400], dp2[200200][20][2], n;

vector<int> combine(int x, int s1, int i1, int j1, int s2, int i2, int j2){
    if (s1>n) return {x};
    vector<int> ret = {x, dp[s1][i1][j1][0]};
    if (s2<=n) ret.push_back(dp[s2][i2][j2][0]);
    return ret;
}

void dfs(int s, int dep, vector<pair<int, int>> C){
    C.emplace_back(dep+1, 0);
    if (s*2<=n){
        dfs(s*2, dep+1, C);
    }
    if (s*2+1<=n){
        C.pop_back();
        C.emplace_back(dep, 1);
        C.emplace_back(dep+1, 0);
        dfs(s*2+1, dep+1, C);
        C.pop_back();
    }
    C.pop_back();

    reverse(C.begin(), C.end());
    int cur = s, cdep = dep;

    for (auto &[i, j]:C){
        while(cdep>i){
            cdep--; cur /= 2;
        }
        assert(cdep==i);
        if (j==1) cur *= 2;

        vector<int> v[4];
        v[0] = combine(a[cur], s*2, dep+1, 0, s*2+1, dep+1, 0);
        v[1] = combine(a[s*2], s*2, i, j, s*2+1, dep+1, 0);
        v[2] = combine(a[s*2+1], s*2, dep+1, 0, s*2+1, i, j);
        v[3] = combine(a[s*2+1], s*2, i, j, s*2+1, dep, 1);

        dp2[s][i][j] = min_element(v, v+4) - v;
        dp[s][i][j] = v[dp2[s][i][j]];


        if (j==1) cur /= 2;
    }
}

void getans(int s, int i, int j, int dep){
    if (s*2>n) return;
    if (s*2+1>n){
        if (dp2[s][i][j]==0) return;
        else swap(a[s], a[s*2]);
        return;
    }

    if (dp2[s][i][j]==0){
        getans(s*2, dep+1, 0, dep+1);
        getans(s*2+1, dep+1, 0, dep+1);
    }
    else if (dp2[s][i][j]==1){
        swap(a[s], a[s*2]);
        getans(s*2, i, j, dep+1);
        getans(s*2+1, dep+1, 0, dep+1);
    }
    else if (dp2[s][i][j]==2){
        swap(a[s], a[s*2+1]);
        getans(s*2, dep+1, 0, dep+1);
        getans(s*2+1, i, j, dep+1);
    }
    else{
        swap(a[s], a[s*2]);
        swap(a[s], a[s*2+1]);
        getans(s*2, i, j, dep+1);
        getans(s*2+1, dep, 1, dep+1);
    }
}

int main(){
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", a+i);
    for (int i=n+1;i<=n*2+1;i++) a[i] = 1e9;

    dfs(1, 1, {{1, 0}});
    getans(1, 1, 0, 1);
    for (int i=1;i<=n;i++) printf("%d ", a[i]);
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'void dfs(int, int, std::vector<std::pair<int, int> >)':
swap.cpp:32:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for (auto &[i, j]:C){
      |                ^
swap.cpp: In function 'int main()':
swap.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
swap.cpp:85:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~

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