Submission #834456

#	Time	Username	Problem	Language	Result	Execution time	Memory
834456		Ronin13	Swap (BOI16_swap)	C++17	68 / 100	1039 ms	237536 KiB

swap

#include <bits/stdc++.h>
#define ll long long  
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 200001;

 vector <vector <int> > ans[200001];
map <pii, int> mp;
int cur[nmax];
int a[nmax];

//vector <vector <int> > g(nmax);
vector <int> vv[nmax];
int n;

void bfs(int s){
    if(2 * s <= n && 2 * s + 1 <= n){
        queue <pii> q;
        q.push({2 * s, 0});
        q.push({2 * s + 1, 1});
        while(!q.empty()){
            int v = q.front().f;
            vv[s].pb(q.front().s);
            q.pop();
            if(2 * v <= n) q.push({2 * v, vv[s].back()});
            if(2 * v + 1 <= n) q.push({2 * v + 1, vv[s].back()});
        }

    }
}

vector <int> A, B;
vector <int> nx, ny;

int opt(int v, int x){
    if(mp[{v, x}] == 0) mp[{v, x}] = ++cur[v], ans[v].pb({});
    else return mp[{v, x}];
    int c = mp[{v, x}];
    if(2 * v > n){
        ans[v][c] = {x};
        return c;
    }
    if(2 * v + 1 > n){
        if(a[2 * v] > x)
            ans[v][c]= {x, a[2 * v]};
        else ans[v][c] = {a[2 * v], x};
        return c;
    }
    vector <int> all = {x, a[2 * v], a[2 *v + 1]};
    sort(all.begin(), all.end());
    if(all[0] == x){
        int xx = opt(2 * v, a[2 * v]);
        int yy =  opt(2 * v+  1, a[ 2* v + 1]);
        A = ans[2 * v][xx];
        B = ans[2 * v + 1][yy];
        ans[v][c].pb(x);
        int inda, indb;
        inda = indb = 0;
        for(int to : vv[v]){
            if(!to) ans[v][c].pb(A[inda]), inda++;
            else ans[v][c].pb(B[indb]), indb++;
        }
        return c;
    }
    if(all[0] == a[2 * v]){
        int xx = opt(2 * v, x);
        int yy = opt(2 * v + 1, a[2 * v + 1]);
        A = ans[2 * v][xx];
        B = ans[2 * v + 1][yy];
        ans[v][c].pb(a[2 * v]);
        int inda, indb;
        inda = indb = 0;
        for(int to : vv[v]){
            if(!to) ans[v][c].pb(A[inda]), inda++;
            else ans[v][c].pb(B[indb]), indb++;
        }
        return c;
    }
    int x1 = opt(2 * v, all[1]), y1 = opt(2 * v+ 1, all[2]);
    int x2 = opt(2 * v, all[2]), y2 = opt(2 * v+ 1, all[1]);
  //  cout << x1 << ' ' << y1 << ' ' <<  x2 << ' ' << y2 << "\n";
     A = ans[2 * v][x1], B = ans[2 *v + 1][y1];
    nx = {all[0]}, ny = {all[0]};
    int inda = 0, indb = 0;
    for(int to : vv[v]){
        if(!to) nx.pb(A[inda]), inda++;
        else nx.pb(B[indb]), indb++;
    }
    A = ans[2 * v][x2];
    B = ans[2 * v + 1][y2];
    inda = 0, indb = 0;
    for(int to : vv[v]){
        if(!to) ny.pb(A[inda]), inda++;
        else ny.pb(B[indb]), indb++;
    }
    ans[v][c] = min(nx, ny);
    return c;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        bfs(i);
        ans[i].pb({});
    }
    int x = opt(1, a[1]);
    //cout << x << ' ';
    for(int to : ans[1][x]) 
        cout << to << ' ';
    return 0;
}

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