Submission #404574

#	Time	Username	Problem	Language	Result	Execution time	Memory
404574		phathnv	자동 인형 (IOI18_doll)	C++11	37 / 100	204 ms	11112 KiB

doll

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

vector<int> a, c, nxt[2], state;

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

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);
    nxt[0].assign(n - 1, 0);
    nxt[1].assign(n - 1, 0);
    state.assign(n - 1, 0);
    build(1, 0, n - 1);
    for(int ind : a){
        int 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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56