Submission #484168

#	Time	Username	Problem	Language	Result	Execution time	Memory
484168		alireza_kaviani	Swap (BOI16_swap)	C++11	68 / 100	1101 ms	212264 KiB

swap

#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "
 
constexpr int N = 2e5 + 10;
 
vector<int> operator*(vector<int> l, vector<int> r) {
    vector<int> res;
    int ll = 0, rr = 0;
    for (int i = 1; ll < (int) l.size(); i *= 2) {
        for (int j = 0; j < i && ll < (int) l.size(); ++j) {
            res.push_back(l[ll++]);
        }
        for (int j = 0; j < i && rr < (int) r.size(); ++j) {
            res.push_back(r[rr++]);
        }
    }
    return res;
}
 
vector<int> operator+(vector<int> l, vector<int> r) {
    for (auto &i : r) {
        l.push_back(i);
    }
    return l;
}
 
int n, a[N];
vector<vector<int>> dp[N];
 
void dfs(int v) {
    int p = (v + 1) * 2 - 1, q = p + 1;
    if (p >= n) {
        for (int x = v, z; x >= 0; x = (x + 1) / 2 - 1) {
            dp[v].push_back(vector<int>{a[x]});
            if (x != v) {
                if ((x + 1) * 2 - 1 != z) {
                    int y = (x + 1) * 2 - 1;
                    dp[v].push_back(vector<int>{a[y]});
                } else {
                    dp[v].push_back({});
                }
            }
            z = x;
        }
        return;
    }
    if (q >= n) {
        dfs(p);
        for (int x = v, z; x >= 0; x = (x + 1) / 2 - 1) {
            dp[v].push_back(min(vector<int>{a[x], a[p]}, vector<int>{a[p], a[x]}));
            if (x != v) {
                if ((x + 1) * 2 - 1 != z) {
                    int y = (x + 1) * 2 - 1;
                    dp[v].push_back(min(vector<int>{a[y], a[p]}, vector<int>{a[p], a[y]}));
                } else {
                    dp[v].push_back({});
                }
            }
            z = x;
        }
        return;
    }
    dfs(p);
    dfs(q);
    int d = 0;
    for (int x = v, z; x >= 0; x = (x + 1) / 2 - 1, d++) {
        dp[v].push_back(vector<int>{a[x]} + (dp[p][0] * dp[q][0]));
        dp[v].back() = min(dp[v].back(), vector<int>{a[p]} + (dp[p][(d + 1) * 2 - 1] * dp[q][0]));
        dp[v].back() = min(dp[v].back(), vector<int>{a[q]} + (dp[p][(d + 1) * 2 - 1] * dp[q][2]));
        dp[v].back() = min(dp[v].back(), vector<int>{a[q]} + (dp[p][0] * dp[q][(d + 1) * 2 - 1]));
        if (x != v) {
            if ((x + 1) * 2 - 1 != z) {
                int y = (x + 1) * 2 - 1;
                dp[v].push_back(vector<int>{a[y]} + (dp[p][0] * dp[q][0]));
                dp[v].back() = min(dp[v].back(), vector<int>{a[p]} + (dp[p][(d + 1) * 2] * dp[q][0]));
                dp[v].back() = min(dp[v].back(), vector<int>{a[q]} + (dp[p][(d + 1) * 2] * dp[q][2]));
                dp[v].back() = min(dp[v].back(), vector<int>{a[q]} + (dp[p][0] * dp[q][(d + 1) * 2]));
            } else {
                dp[v].push_back({});
            }
        }
        z = x;
    }
         
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
     
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
    }
     
    if (n == 1) {
        cout << 1;
        exit(0);
    }
 
    dfs(0);
     
    for (int i = 0; i < n; ++i) {
        cout << dp[0][0][i] + 1 << ' ';
    }
}

Compilation message (stderr)

swap.cpp: In function 'void dfs(int)':
swap.cpp:73:13: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |             if ((x + 1) * 2 - 1 != z) {
      |             ^~
swap.cpp:53:17: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |                 if ((x + 1) * 2 - 1 != z) {
      |                 ^~
swap.cpp:37:17: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |                 if ((x + 1) * 2 - 1 != z) {
      |                 ^~

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