oj.uz

Submission #261617

# Submission time Handle Problem Language Result Execution time Memory
261617 2020-08-11T22:41:42 Z caoash Swap (BOI16_swap) C++14
48 / 100
 1000 ms 74808 KB 
#include <bits/stdc++.h> 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 200005;

int n; int num[MX]; map<pi, vi> dp; 

vi merge(vi &a, int x, vi &b) {
    vi ret;
    ret.pb(x);
    int p1 = 0, p2 = 0;
    for (int i = 0; i < 19; i++) {
        if (p1 < sz(a)) {
            for (int j = 0; j < (1 << i); j++) {
                if (p1 < sz(a)) {
                    ret.pb(a[p1++]);
                }
                else {
                    break;
                }
            } 
        }
        if (p2 < sz(b)) {
            for (int j = 0; j < (1 << i); j++) {
                if (p2 < sz(b)) {
                    ret.pb(b[p2++]);
                } 
                else {
                    break;
                }
            }
        }
    }
    return ret;
}

vi solve(int v, int c) {
    if (!dp[mp(v, c)].empty()) {
        return dp[mp(v, c)];
    }
    int l = 2 * v + 1, r = 2 * v + 2;
    if (l >= n) {
        return dp[mp(v, c)] = {c};
    }
    if (r >= n) {
        vi best; 
        vi fst = solve(l, num[l]);
        best.pb(c);
        for (int x : fst) best.pb(x);
        vi sec = solve(l, c);
        vi sbest;
        sbest.pb(num[l]);
        for (int x : sec) sbest.pb(x);
        return dp[mp(v, c)] = min(best, sbest);
    }
    vi best;
    // no swaps
    vi fst = solve(l, num[l]);
    vi scnd = solve(r, num[r]);
    best = merge(fst, c, scnd);

    // swap left
    if (l < n) {
        fst = solve(l, c), scnd = solve(r, num[r]);
        best = min(best, merge(fst, num[l], scnd));
    }

    // swap right
    if (r < n) {
        fst = solve(l, num[l]);
        scnd = solve(r, c);
        best = min(best, merge(fst, num[r], scnd));
    }

    // swap left, then right
    if (r < n) {
        fst = solve(l, c);
        scnd = solve(r, num[l]);
        best = min(best, merge(fst, num[r], scnd));
    }
    return dp[mp(v, c)] = best;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    solve(0, num[0]); 
    vi ans = dp[mp(0, num[0])];
    for (int i = 0; i < n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 21 ms 1920 KB Output is correct
12 Correct 25 ms 1920 KB Output is correct
13 Correct 21 ms 1912 KB Output is correct
14 Correct 22 ms 1920 KB Output is correct
15 Correct 22 ms 1912 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 21 ms 1920 KB Output is correct
12 Correct 25 ms 1920 KB Output is correct
13 Correct 21 ms 1912 KB Output is correct
14 Correct 22 ms 1920 KB Output is correct
15 Correct 22 ms 1912 KB Output is correct
16 Execution timed out 1090 ms 74808 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 21 ms 1920 KB Output is correct
12 Correct 25 ms 1920 KB Output is correct
13 Correct 21 ms 1912 KB Output is correct
14 Correct 22 ms 1920 KB Output is correct
15 Correct 22 ms 1912 KB Output is correct
16 Execution timed out 1090 ms 74808 KB Time limit exceeded
17 Halted 0 ms 0 KB -