Submission #1150430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150430		polarity	Swap (BOI16_swap)	C++20	10 / 100	0 ms	328 KiB

swap

/**
 * Solution by 1egend (polarity.sh)
 * Date: 2025-02-14
 * Contest: Baltic OI 2016
 * Problem: swap
**/

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 2e5 + 1;
const ll MOD = 1e9 + 7;


/** TOOL: Debug
 *  PURPOSE: Prints various data types to terminal
 *  SOURCE: tourist
*/
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

// O(n logn) space
vector<vector<pii>> dp;
vi tree;
vector<bool> visited;
int nn = 1;

// T(n) = 2T(n/2) + O(n + logn)
// O(n logn) by master theorem
void rec(int node){
    visited[node] = true;
    
    if (node >= nn/2){
        // leaf
        dp[node] = {{1, node}};
        return;
    }

    int a = 2 * node, b = 2 * node + 1;
    int aa = tree[a], bb = tree[b];
    rec(a); rec(b);

    dp[node].pb({1, node});
    if (aa < bb){
        bool found = false;
        rep(i, 0, dp[a].size()){
            pii el = dp[a][i];

            if (!found && (i == dp[a].size() - 1 || dp[a][i + 1].first > aa + 1)){
                found = true;
                dp[node].pb({aa + 1, el.second});
                continue;
            }

            if (found){
                dp[node].pb(el);

            }
        }

        return;
    }

    int p1 = (*prev(upper_bound(all(dp[a]), pii{aa, INT_MAX}))).second;
    int p2 = (*prev(upper_bound(all(dp[b]), pii{aa, INT_MAX}))).second;
    bool found = false;
    rep(i, 0, dp[a].size()){
        pii el = dp[a][i];

        if (el.first >= aa || el.second >= p2){
            break;
        }

        if (!found && (i == dp[a].size() - 1 || dp[a][i + 1].first > bb + 1)){
            found = true;
            dp[node].pb({bb + 1, el.second});
            continue;
        }

        if (found){
            dp[node].pb(el);
        }
    }

    found = false;
    rep(i, 0, dp[b].size()){
        pii el = dp[b][i];

        if (el.second <= p1){
            continue;
        }

        if (!found && (i == dp[a].size() - 1 || dp[a][i + 1].first > aa + 1)){
            found = true;
            dp[node].pb({aa + 1, el.second});
            continue;
        }

        if (found){
            dp[node].pb(el);
        }
    }
}

void extract(int node){
    if (node >= nn/2){
        return;
    }

    int x = tree[node];
    int a = 2 * node, b = 2 * node + 1;
    int aa = tree[a], bb = tree[b];

    if (x < aa && x < bb){
        extract(a); extract(b);
        return;
    }

    if (aa < bb){
        swap(tree[node], tree[a]);
        extract(a); extract(b);
        return;
    }

    tree[node] = bb;

    if (x > aa){
        swap(x, aa);
    }

    int p1 = (*prev(upper_bound(all(dp[a]), pii{x, INT_MAX}))).second;
    int p2 = (*prev(upper_bound(all(dp[b]), pii{aa, INT_MAX}))).second;
    if (p1 < p2){
        tree[a] = x;
        tree[b] = aa;
    } else {
        tree[a] = aa;
        tree[b] = x;
    }

    extract(a); extract(b);
}

void solve(){
    int n; cin >> n;
    while(nn <= n){
        nn *= 2;
    }

    tree = vi(nn, MAX_N);
    dp = vector<vector<pii>>(nn);
    visited = vector<bool>(nn, false);

    rep(i, 0, n){
        cin >> tree[i + 1];
    }

    rec(1);

    rep(i, 1, nn){
        // debug_out(dp[i]);
    }

    visited = vector<bool>(nn, false);

    extract(1);

    rep(i, 1, n + 1){
        cout << tree[i] << " ";
    }

    cout << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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