oj.uz

Submission #563359

# Submission time Handle Problem Language Result Execution time Memory
563359 2022-05-17T02:57:03 Z generic_placeholder_name Swap (BOI16_swap) C++17
48 / 100
 1000 ms 16116 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(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);
        else {
            for(int j = 0; j < idx[i].size(); j++) {
                a[idx[i][j]] = rsv[i][j];
            }
        }
        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++) 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:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j = 0; j < idx[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
swap.cpp:94:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(int j = 0; j < idx[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~
swap.cpp: In function 'int32_t main()':
swap.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             while(p < a.size() || q < b.size()) {
      |                   ~~^~~~~~~~~~
swap.cpp:111:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             while(p < a.size() || q < b.size()) {
      |                                   ~~^~~~~~~~~~
swap.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                    ~~^~~~~~~~~~~
swap.cpp:112:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                                      ~~^~~~~~~~~~~
swap.cpp:123:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  123 |     for(int x: ans) cout << x << ' '; cout << endl;
      |     ^~~
swap.cpp:123:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  123 |     for(int x: ans) cout << x << ' '; cout << endl;
      |                                       ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9636 KB Output is correct
8 Correct 5 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 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9636 KB Output is correct
8 Correct 5 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 10 ms 9832 KB Output is correct
12 Correct 11 ms 9832 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 33 ms 9820 KB Output is correct
15 Correct 34 ms 9940 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9636 KB Output is correct
8 Correct 5 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 10 ms 9832 KB Output is correct
12 Correct 11 ms 9832 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 33 ms 9820 KB Output is correct
15 Correct 34 ms 9940 KB Output is correct
16 Correct 403 ms 16116 KB Output is correct
17 Correct 296 ms 16108 KB Output is correct
18 Correct 440 ms 16080 KB Output is correct
19 Execution timed out 1095 ms 14872 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9636 KB Output is correct
8 Correct 5 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 10 ms 9832 KB Output is correct
12 Correct 11 ms 9832 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 33 ms 9820 KB Output is correct
15 Correct 34 ms 9940 KB Output is correct
16 Correct 403 ms 16116 KB Output is correct
17 Correct 296 ms 16108 KB Output is correct
18 Correct 440 ms 16080 KB Output is correct
19 Execution timed out 1095 ms 14872 KB Time limit exceeded
20 Halted 0 ms 0 KB -