oj.uz

Submission #563380

# Submission time Handle Problem Language Result Execution time Memory
563380 2022-05-17T03:54:11 Z generic_placeholder_name Swap (BOI16_swap) C++17
100 / 100
 576 ms 53684 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

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

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 2e5 + 5;

int n;
int a[N];
vector<int> idx[N];
vector<int> rsv[N];
int conv[N];

constexpr ull M = ULLONG_MAX / 3.141592;

ull hash_order(const vector<int>& a) {
    vector<int> ord(a.size());
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) {return a[i] < a[j];});
    auto seed = ord.size() * M;
    for(int i: ord) seed ^= (i * M) + (seed << 6) + (seed >> 2);
    return seed;
}

gp_hash_table<ull, vector<int>> cache;

vector<int> merge(const vector<int>& a, const vector<int>& b, int i) {
    auto& l = idx[i * 2], r = idx[i * 2 + 1];
    vector<int> ans;
    int p = 0, q = 0;
    while(p < l.size() || q < r.size()) {
        if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
        else ans.pb(a[p++]);
    }
    return ans;
}

int cnt = 0;
vector<int> solve(int i) {
    cnt++;
    if(i > n) return {};
    if(i * 2 > n) return vi{a[i]};
    if(i * 2 == n) {
        return vi{min(a[i], a[i * 2]), max(a[i], a[i * 2])};
    }
    if(i * 4 > n) {
        int x = a[i], y = a[i * 2], z = a[i * 2 + 1];
        if(x < y && x < z) return vi{x, y, z};
        else if(y < x && y < z) return vi{y, x, z};
        else return vi{z, min(x, y), max(x, y)};
    }
    if(a[i] < a[i * 2] && a[i] < a[i * 2 + 1]) {
        vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
        ans.insert(ans.begin(), a[i]);
        return ans;
    }
    else if(a[i * 2] < a[i] && a[i * 2] < a[i * 2 + 1]) {
        swap(a[i], a[i * 2]);
        vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
        ans.insert(ans.begin(), a[i]);
        return ans;
    }
    else {
        swap(a[i], a[i * 2 + 1]);
        rsv[i].clear();
        for(int j: idx[i]) rsv[i].pb(a[j]);
        auto h = hash_order(rsv[i]);
        if(cache.find(h) != cache.end()) {
            auto &v = cache[h];
            vector<int> ans;
            for(int j: v) ans.pb(rsv[i][j]);
            return ans;
        }
        vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
        for(int j = 0; j < idx[i].size(); j++) {
            a[idx[i][j]] = rsv[i][j];
        }
        swap(a[i * 2], a[i * 2 + 1]);
        vector<int> ans2 = merge(solve(i * 2), solve(i * 2 + 1), i);
        if(ans2 < ans) ans.swap(ans2);
        ans.insert(ans.begin(), a[i]);
        vector<int> store;
        for(int j = 0; j < rsv[i].size(); j++) conv[rsv[i][j]] = j;
        for(int j = 0; j < ans.size(); j++) store.pb(conv[ans[j]]);
        cache[h] = store;
        return ans;
    }
}

int32_t main() {
    fastio;
    cin >> n;
    for(int i = n; i >= 1; i--) {
        idx[i].pb(i);
        if(2 * i < n) {
            int p = 0, q = 0;
            auto &a = idx[2 * i], &b = idx[2 * i + 1];
            while(p < a.size() || q < b.size()) {
                if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
                else idx[i].pb(a[p++]);
            }
        }
        else if(2 * i == n) {
            idx[i].insert(idx[i].end(), all(idx[2 * i]));
        }
    }
    //for(int i = 1; i <= n; i++) a[i] = i;
    //reverse(a + 1, a + 1 + n);
    //random_shuffle(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) cin >> a[i];
    auto ans = solve(1);
    //cout << cnt << endl;
    for(int x: ans) cout << x << ' '; cout << endl;
}

Compilation message

swap.cpp: In function 'std::vector<int> merge(const std::vector<int>&, const std::vector<int>&, int)':
swap.cpp:70:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     while(p < l.size() || q < r.size()) {
      |           ~~^~~~~~~~~~
swap.cpp:70:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     while(p < l.size() || q < r.size()) {
      |                           ~~^~~~~~~~~~
swap.cpp:71:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
      |            ~~^~~~~~~~~~~
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 |         if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
      |                              ~~^~~~~~~~~~~
swap.cpp: In function 'std::vector<int> solve(int)':
swap.cpp:114:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for(int j = 0; j < idx[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
swap.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int j = 0; j < rsv[i].size(); j++) conv[rsv[i][j]] = j;
      |                        ~~^~~~~~~~~~~~~~~
swap.cpp:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int j = 0; j < ans.size(); j++) store.pb(conv[ans[j]]);
      |                        ~~^~~~~~~~~~~~
swap.cpp: In function 'int32_t main()':
swap.cpp:137:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             while(p < a.size() || q < b.size()) {
      |                   ~~^~~~~~~~~~
swap.cpp:137:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             while(p < a.size() || q < b.size()) {
      |                                   ~~^~~~~~~~~~
swap.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                    ~~^~~~~~~~~~~
swap.cpp:138:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                                      ~~^~~~~~~~~~~
swap.cpp:152:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  152 |     for(int x: ans) cout << x << ' '; cout << endl;
      |     ^~~
swap.cpp:152:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  152 |     for(int x: ans) cout << x << ' '; cout << endl;
      |                                       ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
27.0 / 27.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 8 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 7 ms 9812 KB Output is correct
15 Correct 9 ms 9812 KB Output is correct
16 Correct 117 ms 18800 KB Output is correct
17 Correct 103 ms 18588 KB Output is correct
18 Correct 107 ms 18912 KB Output is correct
19 Correct 113 ms 20304 KB Output is correct
20 Correct 113 ms 20516 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 8 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 7 ms 9812 KB Output is correct
15 Correct 9 ms 9812 KB Output is correct
16 Correct 117 ms 18800 KB Output is correct
17 Correct 103 ms 18588 KB Output is correct
18 Correct 107 ms 18912 KB Output is correct
19 Correct 113 ms 20304 KB Output is correct
20 Correct 113 ms 20516 KB Output is correct
21 Correct 522 ms 49724 KB Output is correct
22 Correct 531 ms 50532 KB Output is correct
23 Correct 576 ms 51356 KB Output is correct
24 Correct 523 ms 53184 KB Output is correct
25 Correct 524 ms 53684 KB Output is correct