Submission #563353

#	Time	Username	Problem	Language	Result	Execution time	Memory
563353		generic_placeholder_name	Swap (BOI16_swap)	C++17	0 / 100	5 ms	9684 KiB

swap

#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]);
        vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
        rsv[i].clear();
        for(int j: idx[i]) rsv[i].pb(a[i]);
        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 (stderr)

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:86:17: warning: unused variable 'j' [-Wunused-variable]
   86 |         for(int j: idx[i]) rsv[i].pb(a[i]);
      |                 ^
swap.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for(int j = 0; j < idx[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~
swap.cpp: In function 'int32_t main()':
swap.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while(p < a.size() || q < b.size()) {
      |                   ~~^~~~~~~~~~
swap.cpp:108:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while(p < a.size() || q < b.size()) {
      |                                   ~~^~~~~~~~~~
swap.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                    ~~^~~~~~~~~~~
swap.cpp:109:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
      |                                      ~~^~~~~~~~~~~
swap.cpp:120:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  120 |     for(int x: ans) cout << x << ' '; cout << endl;
      |     ^~~
swap.cpp:120:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  120 |     for(int x: ans) cout << x << ' '; cout << endl;
      |                                       ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32