oj.uz

Submission #317503

# Submission time Handle Problem Language Result Execution time Memory
317503 2020-10-29T23:39:22 Z caoash Swap (BOI16_swap) C++14
48 / 100
 1000 ms 11140 KB 
/*
Realize it's a binary tree. Then realize each node can't have that many distinct values.

do dp[node][value], since transition is sum of subtree = sum of depth = nlogn in a binary tree it (shouldn't) MLE/TLE, but
it does! probably because i use map... will fix soon
*/

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h> 
using namespace std;
 
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;
 
struct hash_pair { 
    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; 
    } 
}; 

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

int n; int num[MX]; gp_hash_table<pi, vi, hash_pair> dp; 
 
void merge(vi &best, vi a, int x, vi b) {
    vi ret;
    ret.pb(x);
    int p1 = 0, p2 = 0;
    for (int i = 0; i < 36; 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;
                }
            }
        }
    }
    if (best.empty()) best = ret;
    else best = min(best, 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
    merge(best, solve(l, num[l]), c, solve(r, num[r]));
 
    // swap left
    if (l < n) {
        merge(best, solve(l, c), num[l], solve(r, num[r]));
    }
 
    // swap right
    if (r < n) {
        merge(best, solve(l, num[l]), num[r], solve(r, c));
    }
 
    // swap left, then right
    if (r < n) {
        merge(best, solve(l, c), num[r], solve(r, num[l]));
    }
    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';
}

Compilation message

swap.cpp:9: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("O3")
      | 
swap.cpp:10: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("unroll-loops")
      |

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 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 1 ms 384 KB Output is correct
3 Correct 1 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 1 ms 384 KB Output is correct
3 Correct 1 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 873 ms 2960 KB Output is correct
12 Correct 870 ms 2964 KB Output is correct
13 Correct 893 ms 2960 KB Output is correct
14 Correct 840 ms 3112 KB Output is correct
15 Correct 835 ms 2960 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 1 ms 384 KB Output is correct
3 Correct 1 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 873 ms 2960 KB Output is correct
12 Correct 870 ms 2964 KB Output is correct
13 Correct 893 ms 2960 KB Output is correct
14 Correct 840 ms 3112 KB Output is correct
15 Correct 835 ms 2960 KB Output is correct
16 Execution timed out 1038 ms 11140 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 1 ms 384 KB Output is correct
3 Correct 1 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 873 ms 2960 KB Output is correct
12 Correct 870 ms 2964 KB Output is correct
13 Correct 893 ms 2960 KB Output is correct
14 Correct 840 ms 3112 KB Output is correct
15 Correct 835 ms 2960 KB Output is correct
16 Execution timed out 1038 ms 11140 KB Time limit exceeded
17 Halted 0 ms 0 KB -