Submission #613933

#	Time	Username	Problem	Language	Result	Execution time	Memory
613933		fvogel499	Mechanical Doll (IOI18_doll)	C++17	100 / 100	277 ms	33320 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+2;
    }
    for (int i = p2-1; i < 2*p2-1; i++) {
        assert(0 <= i && i < 2*p2-1);
        xSw[i] = ySw[i] = 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];
            }
            else {
                x = ySw[x];
            }
        }
        assert(0 <= x && x < 2*p2-1);
        to.pb({x, ptr[x]});
        ptr[x] ^= 1;
    }
    int lenSeg = (sz(b)+2)/2;
    int endPos = 2*p2-2;
    int startPos = endPos-lenSeg+1;
    int curToIdx = 0;
    bool used [2*p2-1];
    for (int i = 0; i < 2*p2-1; i++) {
        used[i] = false;
    }
    int otherPurposeX = 2*p2-2;
    while (otherPurposeX >= 0) {
        used[otherPurposeX] = true;
        if (otherPurposeX == 0) break;
        otherPurposeX = (otherPurposeX-1)/2;
    }
    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;
        }
        int x = to[curToIdx].first;
        while (x >= 0) {
            used[x] = true;
            if (x == 0) break;
            x = (x-1)/2;
        }
        curToIdx++;
    }
    set<int> usedSet;
    for (int i = 0; i < 2*p2-1; i++) if (used[i]) usedSet.insert(i);
    map<int, int> usedCompress;
    int kc2 = 0;
    for (int i : usedSet) {
        usedCompress[i] = kc2;
        kc2++;
    }
    vector<int> swCompX(sz(usedSet)), swCompY(sz(usedSet));
    for (int i = 0; i < 2*p2-1; i++) if (used[i]) {
        int iComp = usedCompress[i];
        int xVal = xSw[i];
        int yVal = ySw[i];
        if (usedSet.count(xVal)) {
            swCompX[iComp] = usedCompress[xVal];
        }
        else if (xVal < 0) {
            swCompX[iComp] = xVal;
        }
        else {
            swCompX[iComp] = 0;
        }
        if (usedSet.count(yVal)) {
            swCompY[iComp] = usedCompress[yVal];
        }
        else if (yVal < 0) {
            swCompY[iComp] = yVal;
        }
        else {
            swCompY[iComp] = 0;
        }
    }
    for (int i = 0; i < sz(swCompX); i++) {
        if (swCompX[i] < 0) {
            swCompX[i] *= -1;
        }
        else {
            swCompX[i] = -1-swCompX[i];
        }
        if (swCompY[i] < 0) {
            swCompY[i] *= -1;
        }
        else {
            swCompY[i] = -1-swCompY[i];
        }
    }
    swCompY[usedCompress[2*p2-2]] = 0;
    answer(tOut, swCompX, swCompY);
}

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