Submission #35368

#	Time	Username	Problem	Language	Result	Execution time	Memory
35368		imaxblue	Swap (BOI16_swap)	C++14	100 / 100	159 ms	6508 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, k, t, o,
    a[200005], best[200005], type[200005], p[200005], ans[200005];
bool nd[200005], nr[200005], nu[200005], special;
void del(int R, int N){
    //cout << N << ' ' << R << endl;
    while(N!=0){
        if (N>R)
            nd[N]=1;
        if (special && N>=o){
            type[N]=1;
            best[N]=(1 << 30);
        }
        if (type[N]==2){
            best[N]=best[N*2];
        }
        if (type[N]==3){
            best[N]=min(best[N*2], best[N*2+1]);
        }
        N/=2;
    }
}
int main(){
    cin >> n;
    type[0]=1; best[0]=(1 << 30);
    fox1(l, n){
        cin >> a[l];
        best[l]=l;
        p[a[l]]=l;
    }
    fox1(l, n){
        special=0;
        o=p[l];
        //cout << l << ' ' << nd[l] << ' ';
        if (type[p[l]/2]==0){
            //cout << "*";
            type[p[l]/2]=2+(p[l]%2);
            ans[p[l]/2]=l;
            if (p[l]%2==0) nr[p[l]/2]=1;
            del(p[l]/2, p[l]/2);
        //fox1(l, n) cout << best[l] << ' '; cout << endl;
            continue;
        }
        special=1;
        if (nd[p[l]]){
            p[l]/=2;
            nr[p[l]/2]=1;
            p[l]=p[l]*2+1;
            nd[p[l]]=1;
        } else if (p[l]%2==0 && best[p[l]/2]<best[p[l]]){
            p[l]/=2;
            nr[p[l]/2]=1;
        }
        t=best[p[l]];
        ans[t]=l;
        type[t]=1;
        best[t]=(1 << 30);
        del(p[l], t);
        //fox1(l, n) cout << best[l] << ' '; cout << endl;
    }
    fox1(l, n) cout << ans[l] << ' ';
    return 0;
}

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