Submission #613847

#	Time	Username	Problem	Language	Result	Execution time	Memory
613847		fvogel499	Mechanical Doll (IOI18_doll)	C++17	37 / 100	124 ms	11480 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define vi vector<int>

void create_circuit(int nbT, std::vector<int> b) {
    vi tOut(nbT+1, -1);
    int p2 = 1;
    while (p2*2 <= sz(b)) p2 *= 2;
    vi xSw(2*p2-1);
    vi ySw(2*p2-1);
    for (int i = 0; i < p2-1; i++) {
        assert(0 <= i && i < 2*p2-1);
        xSw[i] = -2*(i+1);
        ySw[i] = -2*(i+1)-1;
    }
    for (int i = p2-1; i < 2*p2-1; i++) {
        assert(0 <= i && i < 2*p2-1);
        xSw[i] = ySw[i] = -1;
    }
    ySw[2*p2-2] = 0;
    vi ptr(2*p2-1);
    for (int i = 0; i < p2/2; i++) ptr[i] = 0;
    vector<pair<int, int>> to;
    assert(sz(b) <= p2*2-1);
    for (int i = 0; i < p2*2-1; i++) {
        int x = 0;
        while (x < p2-1) {
            assert(0 <= i && i < 2*p2-1);
            ptr[x] ^= 1;
            if (ptr[x] == 1) {
                x = -xSw[x]-1;
            }
            else {
                x = -ySw[x]-1;
            }
        }
        assert(0 <= x && x < 2*p2-1);
        to.pb({x, ptr[x]});
        ptr[x] ^= 1;
    }
    int lenSeg = (sz(b)+1/2);
    int startPos = p2-1;
    int endPos = startPos+lenSeg-1;
    int curToIdx = 0;
    for (int i : b) {
        while (curToIdx < sz(to) && !(startPos <= to[curToIdx].first && to[curToIdx].first <= endPos)) {
            curToIdx++;
        }
        assert(curToIdx < sz(to));
        if (to[curToIdx].second == 0) {
            xSw[to[curToIdx].first] = i;
        }
        else {
            ySw[to[curToIdx].first] = i;
        }
        curToIdx++;
    }
    answer(tOut, xSw, ySw);
}

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