oj.uz

Submission #261616

# Submission time Handle Problem Language Result Execution time Memory
261616 2020-08-11T22:41:13 Z caoash Swap (BOI16_swap) C++14
21 / 100
 1000 ms 2964 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;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();

struct chash { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2 ^ RANDOM; 
    } 
};

int n; int num[MX]; gp_hash_table<pi, vi, chash> 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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 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 892 ms 2964 KB Output is correct
12 Correct 940 ms 2912 KB Output is correct
13 Correct 963 ms 2960 KB Output is correct
14 Execution timed out 1016 ms 2960 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 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 892 ms 2964 KB Output is correct
12 Correct 940 ms 2912 KB Output is correct
13 Correct 963 ms 2960 KB Output is correct
14 Execution timed out 1016 ms 2960 KB Time limit exceeded
15 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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 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 892 ms 2964 KB Output is correct
12 Correct 940 ms 2912 KB Output is correct
13 Correct 963 ms 2960 KB Output is correct
14 Execution timed out 1016 ms 2960 KB Time limit exceeded
15 Halted 0 ms 0 KB -