oj.uz

Submission #538876

# Submission time Handle Problem Language Result Execution time Memory
538876 2022-03-17T23:19:29 Z qwerasdfzxcl Swap (BOI16_swap) C++14
0 / 100
 127 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> dp[400400][20][2];
int a[400400], 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};
    if (s2>n){
        for (auto &y:dp[s1][i1][j1]) ret.push_back(y);
        return ret;
    }

    int pt = 0;
    for (int t=1;;t*=2){
        for (int i=0;i<t;i++){
            if (pt+i>=(int)dp[s1][i1][j1].size()) break;
            ret.push_back(dp[s1][i1][j1][pt+i]);
        }
        for (int i=0;i<t;i++){
            if (pt+i>=(int)dp[s2][i2][j2].size()) break;
            ret.push_back(dp[s2][i2][j2][pt+i]);
        }

        pt += t;
        if (pt>=(int)dp[s1][i1][j1].size() && pt>=(int)dp[s2][i2][j2].size()) break;
    }
    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);

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

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

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}});
    for (auto &x:dp[1][1][0]) printf("%d ", x);
    return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -