oj.uz

Submission #563372

# Submission time Handle Problem Language Result Execution time Memory
563372 2022-05-17T03:11:50 Z generic_placeholder_name Swap (BOI16_swap) C++17
48 / 100
 1000 ms 16060 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];

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]);
        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]);
        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:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while(p < l.size() || q < r.size()) {
      |           ~~^~~~~~~~~~
swap.cpp:56:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while(p < l.size() || q < r.size()) {
      |                           ~~^~~~~~~~~~
swap.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
      |            ~~^~~~~~~~~~~
swap.cpp:57:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         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:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j = 0; j < idx[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
swap.cpp: In function 'int32_t main()':
swap.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while(p < a.size() || q < b.size()) {
      |                   ~~^~~~~~~~~~
swap.cpp:112:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while(p < a.size() || q < b.size()) {
      |                                   ~~^~~~~~~~~~
swap.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                    ~~^~~~~~~~~~~
swap.cpp:113:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                                      ~~^~~~~~~~~~~
swap.cpp:127:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  127 |     for(int x: ans) cout << x << ' '; cout << endl;
      |     ^~~
swap.cpp:127:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  127 |     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 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9716 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 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 7 ms 9652 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 7 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 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 7 ms 9652 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 11 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 16 ms 9840 KB Output is correct
15 Correct 16 ms 9840 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 7 ms 9652 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 11 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 16 ms 9840 KB Output is correct
15 Correct 16 ms 9840 KB Output is correct
16 Correct 230 ms 15820 KB Output is correct
17 Correct 164 ms 15956 KB Output is correct
18 Correct 225 ms 16060 KB Output is correct
19 Execution timed out 1076 ms 15572 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9716 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 7 ms 9652 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 11 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 16 ms 9840 KB Output is correct
15 Correct 16 ms 9840 KB Output is correct
16 Correct 230 ms 15820 KB Output is correct
17 Correct 164 ms 15956 KB Output is correct
18 Correct 225 ms 16060 KB Output is correct
19 Execution timed out 1076 ms 15572 KB Time limit exceeded
20 Halted 0 ms 0 KB -