Submission #1199846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199846		ByeWorld	Mechanical Doll (IOI18_doll)	C++20	100 / 100	87 ms	16784 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 8e5+15;
const int SQRT = 560;
const int INF = 1e9+10;
const int MOD = 998244353;
const int LOG = 20;

int n, m;
int a[MAXN], x[MAXN], y[MAXN], use[MAXN];
vector<int> C, X, Y;
int lg, node, num;

void dfs(int id, int dep){
    if(dep == lg){
        node++;
        if(node > num-n) use[id] = 1;
        else use[id] = 0;
        return;
    }
    dfs(lf, dep+1); dfs(rg, dep+1);
    use[id] = use[lf]+use[rg];
}
void trav(int id, int dep){
    if(dep+1 == lg){
        if(use[lf]) x[id] = lf; 
        else x[id] = -1;
        if(use[rg]) y[id] = rg;
        else y[id] = -1;
        return;
    }
    if(!use[lf] && !use[rg]) return;
    if(use[lf]) trav(lf, dep+1), x[id] = lf; 
    else x[id] = -1;
    if(use[rg]) trav(rg, dep+1), y[id] = rg;
    else y[id] = -1;
}

int name[MAXN], las[MAXN];
bool ty[MAXN];
int idx, tim;
int ansx[MAXN], ansy[MAXN];

void bd(int nw, int dep){
    if(dep == lg) return;
    ++tim;
    name[nw] = tim;

    if(x[nw] != -1){
        bd(x[nw], dep+1);
        ansx[name[nw]] = name[x[nw]];
    } else ansx[name[nw]] = -1;

    if(y[nw] != -1){
        bd(y[nw], dep+1);
        ansy[name[nw]] = name[y[nw]];
    } else ansy[name[nw]] = -1;
}
void move(int nw, int dep, int mask){
    if(nw == -1){
        int bit = lg-dep;
        for(int i=0; i<(1<<bit); i++)
            las[mask + (i<<dep)] = -1;
        return;
    }
    if(dep == lg){ // nw -> mask
        las[mask] = nw;
        return;
        // name[nw] = n+n+a[idx];
    }

    move(x[nw], dep+1, mask); move(y[nw], dep+1, mask+(1<<dep));
}
void create_circuit(int M, std::vector<int> A) {
    n = A.size(); m = M;
    for(int i=0; i<n; i++) a[i] = A[i];
    a[n] = 0; n++;

    num = 1;
    while(num < n){
        lg++; num *= 2;
    }

    C.resize(m+1);
    for(int i=0; i<=m; i++) C[i] = -1;
    
    dfs(1, 0);
    trav(1,0);
    // for(int i=1; i<=3; i++){
    //     cout << i << ' ' << x[i] << ' ' << y[i] << "xy\n";
    // }

    move(1, 0, 0);
    for(int i=0; i<num; i++){ // mask ini akhirannya kemana
        if(las[i] == -1) continue;
        name[las[i]] = n+n+a[idx];
        idx++;
    }
    bd(1, 0);
    // cout << "xx\n";

    X.resize(tim); Y.resize(tim);
    for(int i=0; i<tim; i++){ //i+1 ke mana
        X[i] = ansx[i+1], Y[i] = ansy[i+1];
        if(X[i] != -1){
            if(X[i] < n+n) X[i] = -X[i];
            else X[i] -= n+n;
        }
        if(Y[i] != -1){
            if(Y[i] < n+n) Y[i] = -Y[i];
            else Y[i] -= n+n;
        }
        // cout << i+1 << ' ' << X[i] << ' ' << Y[i] << " pp\n";
    } 
    answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56