Submission #328639

#	Time	Username	Problem	Language	Result	Execution time	Memory
328639		doowey	Swap (BOI16_swap)	C++14	68 / 100	492 ms	262144 KiB

swap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 1;
const int LOG = 18;
vector<int> dp[2*N*LOG];
int idx = 0;

int n;
int a[N];

map<int, int> ids[N]; // looks bad but first subtasks should work

void unite(vector<int> &c, vector<int> &a, vector<int> &b){
    int q = 1;
    int f0 = 0, f1 = 0;
    int dq = c.size() + a.size() + b.size();
    int sh = c.size();
    c.resize(dq);
    while(f0 < a.size() || f1 < b.size()){
        for(int j = 0; j < q; j ++ ){
            if(f0 < a.size()){
                c[sh]=a[f0];
                sh++;
                f0 ++ ;
            }
        }
        for(int j = 0 ; j < q; j ++ ){
            if(f1 < b.size()){
                c[sh]=b[f1];
                sh++;
                f1 ++ ;
            }
        }
        q <<= 1;
    }
}

const int INF = (int)1e9;

void solve(int id, int x){
    if(x == INF) return;
    if(ids[id].count(x)) return;
    idx ++ ;
    ids[id][x] = idx;
    int cid = idx;
    if(id * 2 > n){
        dp[cid]={x};
        return;
    }
    if(id * 2 + 1 > n){
        if(x < a[id * 2]){
            dp[cid]={x,a[id*2]};
        }
        else{
            dp[cid]={a[id*2],x};
        }
        return;
    }
    int fa = a[id*2];
    int fb = a[id*2+1];
    if(x < fa && x < fb){
        solve(id*2, fa);
        solve(id*2+1, fb);
        vector<int> sol = {x};
        unite(sol,dp[ids[id*2][fa]],dp[ids[id*2+1][fb]]);
        dp[cid]=sol;
        return;
    }
    if(fa < x && fa < fb){
        solve(id*2, x);
        solve(id*2+1, fb);
        vector<int>sol = {fa};
        unite(sol, dp[ids[id*2][x]], dp[ids[id*2+1][fb]]);
        dp[cid]=sol;
        return;
    }
    solve(id*2, x);
    solve(id*2+1, fa);
    solve(id*2, fa);
    solve(id*2+1, x);
    // 2n log n states max
    vector<int> aa = {fb}, bb = {fb};
    unite(aa, dp[ids[id*2][x]], dp[ids[id*2+1][fa]]);
    unite(bb, dp[ids[id*2][fa]], dp[ids[id*2+1][x]]);
    dp[cid]=min(aa, bb);
}

int main(){
    fastIO;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    solve(1, a[1]);
    for(auto x : dp[ids[1][a[1]]])
        cout << x << " ";
    cout << "\n";
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'void unite(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(f0 < a.size() || f1 < b.size()){
      |           ~~~^~~~~~~~~~
swap.cpp:29:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(f0 < a.size() || f1 < b.size()){
      |                            ~~~^~~~~~~~~~
swap.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             if(f0 < a.size()){
      |                ~~~^~~~~~~~~~
swap.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(f1 < b.size()){
      |                ~~~^~~~~~~~~~

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