oj.uz

Submission #484168

# Submission time Handle Problem Language Result Execution time Memory
484168 2021-11-02T09:26:05 Z alireza_kaviani Swap (BOI16_swap) C++11
68 / 100
 1000 ms 212264 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4996 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4996 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4940 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4996 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4940 KB Output is correct
11 Correct 10 ms 6220 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 10 ms 6220 KB Output is correct
14 Correct 9 ms 6160 KB Output is correct
15 Correct 10 ms 6204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4996 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4940 KB Output is correct
11 Correct 10 ms 6220 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 10 ms 6220 KB Output is correct
14 Correct 9 ms 6160 KB Output is correct
15 Correct 10 ms 6204 KB Output is correct
16 Correct 692 ms 102272 KB Output is correct
17 Correct 692 ms 102308 KB Output is correct
18 Correct 691 ms 102280 KB Output is correct
19 Correct 686 ms 102432 KB Output is correct
20 Correct 687 ms 102364 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4996 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4940 KB Output is correct
11 Correct 10 ms 6220 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 10 ms 6220 KB Output is correct
14 Correct 9 ms 6160 KB Output is correct
15 Correct 10 ms 6204 KB Output is correct
16 Correct 692 ms 102272 KB Output is correct
17 Correct 692 ms 102308 KB Output is correct
18 Correct 691 ms 102280 KB Output is correct
19 Correct 686 ms 102432 KB Output is correct
20 Correct 687 ms 102364 KB Output is correct
21 Execution timed out 1101 ms 212264 KB Time limit exceeded
22 Halted 0 ms 0 KB -