Submission #35297

#	Time	Username	Problem	Language	Result	Execution time	Memory
35297		imaxblue	Swap (BOI16_swap)	C++14	0 / 100	1000 ms	5920 KiB

swap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, t, tp,
    type[200005], best[200005], par[200005], p[200005], a[200005];
int swp(int X, int Y){
    t=p[X]; p[X]=p[Y]; p[Y]=t;
    a[p[X]]=X; a[p[Y]]=Y;
}
int get(int N){
    int P=par[N];
    N=p[N];
    //cout << best[0] << ' ' << N << ' ' << P << endl;
    int hi=N;
    bool f;
    while(N!=P){
        f=N%2;
        N=N/2;
        if (!(f && type[N]==2))
        hi=min(hi, best[N]);
    };
    return hi;
}
int del(int N){
    best[N]=(1 << 30);
    while(N!=0){
        if (type[N]==2){
            best[N]=best[N*2];
        }
        if (type[N]==3){
            best[N]=min(best[N*2], best[N*2+1]);
        }
        N=N/2;
    }
}
int main(){
    cin >> n;
    type[0]=1; best[0]=(1<<30);
    fox1(l, n){
        best[l]=l;
        cin >> a[l];
        p[a[l]]=l;
        par[a[l]]=l/2;
    }
    //fox1(l, n) cout << par[l] << ' ' ;cout << endl;
    fox1(l, n){
        t=get(l);
        //cout << l << ' ' << p[l] << ' ' << t << endl;
        tp=(p[l]%2);
        swp(a[t], l);
        if (t==par[l]){
            type[t]=2+tp;
            del(t);
        //fox1(l, 10) cout << a[l] << ' '; cout << endl;
        //fox1(l, 6) cout << best[l] << ' '; cout << endl;
            continue;
        }
        type[t]=1;
        del(t);
        //fox1(l, 6) cout << best[l] << ' '; cout << endl;
        //fox1(l, 10) cout << a[l] << ' '; cout << endl;
    }
    fox1(l, n) cout << a[l] << ' ';
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int swp(int, int)':
swap.cpp:32:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int del(int)':
swap.cpp:58:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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