Submission #404580

#	Time	Username	Problem	Language	Result	Execution time	Memory
404580		phathnv	Mechanical Doll (IOI18_doll)	C++11	100 / 100	220 ms	13520 KiB

doll

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

int numNode, skiped;
vector<int> a, c, nxt[2], state, nodeInd;
vector<bool> mark;

void init(int id, int l, int r){
    if (l + 1 == r){
        mark[id] = (a[l] == -1 && a[r] == -1);
        return;
    }
    int mid = (l + r) >> 1;
    init(id << 1, l, mid);
    init(id << 1 | 1, mid + 1, r);
    mark[id] = mark[id << 1] && mark[id << 1 | 1];
}

void build(int id, int l, int r){
    if (mark[id]){
        skiped += r - l + 1;
        return;
    }
    nodeInd[id] = ++numNode;
    if (l + 1 == r)
        return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    nxt[0][nodeInd[id] - 1] = mark[id << 1]? -1 : -nodeInd[id << 1];
    nxt[1][nodeInd[id] - 1] = mark[id << 1 | 1]? -1 : -nodeInd[id << 1 | 1];
}

void create_circuit(int m, vector<int> _a) {
    a = _a;
    a.push_back(0);
    reverse(a.begin(), a.end());
    int n = 1;
    while (n < (int) a.size())
        n *= 2;
    while ((int) a.size() < n)
        a.push_back(-1);
    reverse(a.begin(), a.end());
    c.assign(m + 1, -1);
    mark.assign(n, 0);
    nodeInd.assign(n, 0);
    nxt[0].assign(n, 0);
    nxt[1].assign(n, 0);
    state.assign(n, 0);
    init(1, 0, n - 1);
    build(1, 0, n - 1);
    nxt[0].resize(numNode);
    nxt[1].resize(numNode);
    state.resize(numNode);

    for(int i = skiped; i < n; i++){
        int ind = a[i], cur = 1;
        while (nxt[state[cur - 1]][cur - 1] < 0){
            int tmp = -nxt[state[cur - 1]][cur - 1];
            state[cur - 1] ^= 1;
            cur = tmp;
        }
        nxt[state[cur - 1]][cur - 1] = ind;
        state[cur - 1] ^= 1;
    }
    assert(*max_element(state.begin(), state.end()) == 0);
    answer(c, nxt[0], nxt[1]);
}

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