Submission #1077673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077673		s_tree	Mechanical Doll (IOI18_doll)	C++17	100 / 100	117 ms	21468 KiB

doll

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

const int N = 1e6;
vector<int> x(N), y(N), c(N);
vector<int> state(N);
int nodecnt = 0, n, pw = 1;

int build(int l, int r) {
    if (l >= r) return 0;
    if (r < pw - n) {
        return -1;
    }
    int mid = (l + r) / 2;
    int cur = ++nodecnt;
    x[cur - 1] = build(l, mid);
    y[cur - 1] = build(mid + 1, r);
    return -cur;
}

void ins(int i, int val) {
    if (state[-i]) {
        state[-i] ^= 1;
        if (y[-i - 1] == 0) {
            y[-i - 1] = val;
        } else {
            ins(y[-i - 1], val);
        }
    } else {
        state[-i] ^= 1;
        if (x[-i - 1] == 0) {
            x[-i - 1] = val;
        } else {
            ins(x[-i - 1], val);
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    pw = 1;
    n = A.size();
    c = vector<int>(M + 1, -1);
    while (pw < n) {
        pw *= 2;
    }
    build(0, pw - 1);
    for (int i = 1; i < n; i++) {
        ins(-1, A[i]);
    }
    if (n % 2 == 1) ins(-1, -1);
    ins(-1, 0);
    c[0] = A[0]; 
   	x.resize(nodecnt+1);
		y.resize(nodecnt+1);

    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