Submission #823599

#	Time	Username	Problem	Language	Result	Execution time	Memory
823599		someone	Mechanical Doll (IOI18_doll)	C++14	84 / 100	103 ms	9888 KiB

doll

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

const int INF = 1e9 + 42;

int id = 0, n;
vector<int> nxt[2], state;

int tree(int lvl, int deb) {
    if(deb >= n) return -INF;
    if(lvl == 0) return 0;
    lvl--;
    int mid = deb + (1 << (lvl));
    int right = tree(lvl, deb), left = tree(lvl, mid);
    nxt[0].push_back(left);
    nxt[1].push_back(right);
    return --id;
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    n = (int)A.size();
    vector<int> C(M + 1);
    int len = 0;
    while((1 << len) <= n) len++;
    tree(len, 0);
    int sz = (int)nxt[0].size();
    for (int i = 0; i <= M; ++i)
        C[i] = -sz;
    for(int i = 0; i < sz; i++) {
        if(nxt[0][i] == -INF)
            nxt[0][i] = -sz;
        if(nxt[1][i] == -INF)
            nxt[1][i] = -sz;
    }
    state.resize((int)nxt[0].size());
    id = 0;
    int i = sz-1;
    while(i != -1) {
        int nex = -nxt[state[i]][i]-1;
        if(nxt[state[i]][i] == 0) {
            nxt[state[i]][i] = A[id++];
            nex = sz-1;
            if(nxt[state[i]][i] == 0) nex = -1;
        }
        state[i] = 1 - state[i];
        i = nex;
    }
    answer(C, nxt[0], nxt[1]);
}

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