Submission #138889

#	Time	Username	Problem	Language	Result	Execution time	Memory
138889		evpipis	Mechanical Doll (IOI18_doll)	C++14	100 / 100	186 ms	10768 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int len = 3e5+5;
int lef[len], rig[len], arr[len], vis[len], cnt, pos;

int build(int l, int r){
    if (l == r)
        return l;

    int mid = (l+r)/2, cur = ++cnt;
    lef[cur] = build(l, mid);
    rig[cur] = build(mid+1, r);

    //printf("build: l = %d, r = %d\n", l, r);
    //printf("switch = %d, lef = %d, rig = %d\n", -cur, lef[cur], rig[cur]);
    return -cur;
}

int fix(int num, int lim, int j){
    int cur = ++cnt;
    if (num&(1<<j))
        lef[cur] = build(lim+1, lim+(1<<j)), num -= (1<<j), lim += (1<<j);
    else
        lef[cur] = -1;

    if (j == 0)
        rig[cur] = 0;
    else
        rig[cur] = fix(num, lim, j-1);

    //printf("fix: j = %d\n", j);
    //printf("cur = %d, lef = %d, rig = %d\n", -cur, lef[cur], rig[cur]);
    return -cur;
}

void create_circuit(int m, vector<int> A) {
    int n = A.size();
    for (int i = 1; i <= n; i++)
        arr[i] = A[i-1];

    int j = 0;
    while ((1<<j) <= n)
        j++;

    vector<int> C(m+1);
    C[0] = fix(n, 0, j-1);
    for (int i = 1; i <= m; i++)
        C[i] = C[0];

    //printf("c0 = %d\n", C[0]);

    int cur = -1;
    while (cur != 0){
        //printf("cur = %d\n", cur);
        if (!vis[-cur]){
            vis[-cur] ^= 1;
            if (lef[-cur] >= 1)
                lef[-cur] = arr[++pos], cur = C[0];
            else
                cur = lef[-cur];
        }
        else{
            vis[-cur] ^= 1;
            if (rig[-cur] >= 1)
                rig[-cur] = arr[++pos], cur = C[0];
            else
                cur = rig[-cur];
        }
    }

    vector<int> X(cnt), Y(cnt);
    for (int i = 0; i < cnt; i++)
        X[i] = lef[i+1], Y[i] = rig[i+1];

    answer(C, X, Y);
}
/*
4 4
1 2 1 3
*/

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