oj.uz

Submission #741449

# Submission time Handle Problem Language Result Execution time Memory
741449 2023-05-14T05:49:13 Z GrindMachine Swap (BOI16_swap) C++17
68 / 100
 535 ms 262144 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://usaco.guide/problems/baltic-oi-2016swap/solution
hidden tcs

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> merge(int root, vector<int> v1, vector<int> v2) {
    vector<int> v3;
    v3.pb(root);

    int curr = 1;
    int ptr = 0;

    while (ptr < sz(v1) or ptr < sz(v2)) {
        rep(j, curr) {
            if (ptr < sz(v1)) {
                v3.pb(v1[ptr]);
            }
            ptr++;
        }

        ptr -= curr;

        rep(j, curr) {
            if (ptr < sz(v2)) {
                v3.pb(v2[ptr]);
            }
            ptr++;
        }

        curr *= 2;
    }

    return v3;
}

vector<int> a(N * 2, inf1);
int n;
Tree<int> states[N];

void gen_states(int i, int j) {
    if (i > n) return;
    if (states[i].find(j) != states[i].end()) return;

    states[i].insert(j);

    int l = 2 * i, r = 2 * i + 1;

    if (j < a[l] and j < a[r]) {
        gen_states(l, a[l]);
        gen_states(r, a[r]);
    }
    else if (a[l] < j and a[l] < a[r]) {
        states[i].insert(a[l]);
        gen_states(l, j);
        gen_states(r, a[r]);
    }
    else {
        states[i].insert(a[r]);
        gen_states(l, a[l]);
        gen_states(r, j);
        gen_states(l, j);
        gen_states(r, a[l]);
    }
}

vector<int> dp[N][40];

void solve(int test_case)
{
    cin >> n;
    rep1(i, n) cin >> a[i];

    gen_states(1, a[1]);

    rev(i, n, 1) {
        int siz = sz(states[i]);

        int ind1 = -1, ind2 = -1, ind3 = -1;
        int l = 2 * i, r = 2 * i + 1;

        trav(j, states[i]) {
            ind1++;

            if (l > n and r > n) {
                dp[i][ind1] = {j};
            }
            else if (r > n) {
                dp[i][ind1] = {min(j, a[l]), max(j, a[l])};
            }
            else {
                if (j < a[l] and j < a[r]) {
                    // no swap
                    ind2 = states[l].order_of_key(a[l]);
                    ind3 = states[r].order_of_key(a[r]);
                    dp[i][ind1] = merge(j, dp[l][ind2], dp[r][ind3]);
                }
                else if (a[l] < j and a[l] < a[r]) {
                    // swap with left
                    ind2 = states[l].order_of_key(j);
                    ind3 = states[r].order_of_key(a[r]);
                    dp[i][ind1] = merge(a[l], dp[l][ind2], dp[r][ind3]);
                }
                else {
                    // swap with right
                    ind2 = states[l].order_of_key(a[l]);
                    ind3 = states[r].order_of_key(j);
                    dp[i][ind1] = merge(a[r], dp[l][ind2], dp[r][ind3]);

                    // swap with left and swap with right
                    ind2 = states[l].order_of_key(j);
                    ind3 = states[r].order_of_key(a[l]);
                    amin(dp[i][ind1], merge(a[r], dp[l][ind2], dp[r][ind3]));
                }
            }
        }

        if (l <= n) {
            rep(j, 40) {
                dp[l][j].clear();
                dp[l][j].shrink_to_fit();
            }
        }

        if (r <= n) {
            rep(j, 40) {
                dp[r][j].clear();
                dp[r][j].shrink_to_fit();
            }
        }
    }

    int ind = states[1].order_of_key(a[1]);
    auto ans = dp[1][ind];

    trav(x, ans) cout << x << " ";
    cout << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

swap.cpp: In function 'std::vector<int> merge(int, std::vector<int>, std::vector<int>)':
swap.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     while (ptr < sz(v1) or ptr < sz(v2)) {
      |                ^
swap.cpp:71:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     while (ptr < sz(v1) or ptr < sz(v2)) {
      |                                ^
swap.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             if (ptr < sz(v1)) {
      |                     ^
swap.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if (ptr < sz(v2)) {
      |                     ^
swap.cpp: In function 'void solve(int)':
swap.cpp:134:13: warning: unused variable 'siz' [-Wunused-variable]
  134 |         int siz = sz(states[i]);
      |             ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 205392 KB Output is correct
2 Correct 105 ms 205324 KB Output is correct
3 Correct 121 ms 205308 KB Output is correct
4 Correct 110 ms 205520 KB Output is correct
5 Correct 105 ms 205312 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 205392 KB Output is correct
2 Correct 105 ms 205324 KB Output is correct
3 Correct 121 ms 205308 KB Output is correct
4 Correct 110 ms 205520 KB Output is correct
5 Correct 105 ms 205312 KB Output is correct
6 Correct 99 ms 205360 KB Output is correct
7 Correct 100 ms 205364 KB Output is correct
8 Correct 103 ms 205372 KB Output is correct
9 Correct 112 ms 205392 KB Output is correct
10 Correct 109 ms 205392 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 205392 KB Output is correct
2 Correct 105 ms 205324 KB Output is correct
3 Correct 121 ms 205308 KB Output is correct
4 Correct 110 ms 205520 KB Output is correct
5 Correct 105 ms 205312 KB Output is correct
6 Correct 99 ms 205360 KB Output is correct
7 Correct 100 ms 205364 KB Output is correct
8 Correct 103 ms 205372 KB Output is correct
9 Correct 112 ms 205392 KB Output is correct
10 Correct 109 ms 205392 KB Output is correct
11 Correct 122 ms 205552 KB Output is correct
12 Correct 103 ms 205516 KB Output is correct
13 Correct 109 ms 205524 KB Output is correct
14 Correct 108 ms 206048 KB Output is correct
15 Correct 103 ms 205928 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 205392 KB Output is correct
2 Correct 105 ms 205324 KB Output is correct
3 Correct 121 ms 205308 KB Output is correct
4 Correct 110 ms 205520 KB Output is correct
5 Correct 105 ms 205312 KB Output is correct
6 Correct 99 ms 205360 KB Output is correct
7 Correct 100 ms 205364 KB Output is correct
8 Correct 103 ms 205372 KB Output is correct
9 Correct 112 ms 205392 KB Output is correct
10 Correct 109 ms 205392 KB Output is correct
11 Correct 122 ms 205552 KB Output is correct
12 Correct 103 ms 205516 KB Output is correct
13 Correct 109 ms 205524 KB Output is correct
14 Correct 108 ms 206048 KB Output is correct
15 Correct 103 ms 205928 KB Output is correct
16 Correct 181 ms 214536 KB Output is correct
17 Correct 193 ms 214484 KB Output is correct
18 Correct 184 ms 214844 KB Output is correct
19 Correct 459 ms 252320 KB Output is correct
20 Correct 460 ms 251980 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 205392 KB Output is correct
2 Correct 105 ms 205324 KB Output is correct
3 Correct 121 ms 205308 KB Output is correct
4 Correct 110 ms 205520 KB Output is correct
5 Correct 105 ms 205312 KB Output is correct
6 Correct 99 ms 205360 KB Output is correct
7 Correct 100 ms 205364 KB Output is correct
8 Correct 103 ms 205372 KB Output is correct
9 Correct 112 ms 205392 KB Output is correct
10 Correct 109 ms 205392 KB Output is correct
11 Correct 122 ms 205552 KB Output is correct
12 Correct 103 ms 205516 KB Output is correct
13 Correct 109 ms 205524 KB Output is correct
14 Correct 108 ms 206048 KB Output is correct
15 Correct 103 ms 205928 KB Output is correct
16 Correct 181 ms 214536 KB Output is correct
17 Correct 193 ms 214484 KB Output is correct
18 Correct 184 ms 214844 KB Output is correct
19 Correct 459 ms 252320 KB Output is correct
20 Correct 460 ms 251980 KB Output is correct
21 Correct 535 ms 243412 KB Output is correct
22 Correct 515 ms 244424 KB Output is correct
23 Correct 487 ms 244488 KB Output is correct
24 Runtime error 232 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -