제출 #538878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538878		qwerasdfzxcl	Swap (BOI16_swap)	C++14	68 / 100	1091 ms	194648 KiB

swap

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> dp[200200][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 _delete(int s){
    if (s>n) return;
    for (int i=0;i<20;i++){
        dp[s][i][0].clear();
        dp[s][i][1].clear();
        dp[s][i][0].shrink_to_fit();
        dp[s][i][1].shrink_to_fit();
    }
}

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;
    }

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

컴파일 시 표준 에러 (stderr) 메시지

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

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