Submission #363516

#	Time	Username	Problem	Language	Result	Execution time	Memory
363516		mjhmjh1104	Mechanical Doll (IOI18_doll)	C++14	100 / 100	183 ms	10972 KiB

doll

#include "doll.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool sw[400006];
int n, s;
vector<int> c, a, b;

bool goForward(int &x) {
    if (x >= 0) {
        if (c[x] == -2e9) return false;
        x = c[x];
    } else {
        if (!sw[-x - 1]) {
            if (a[-x - 1] == -2e9) return false;
            sw[-x - 1] = true;
            x = a[-x - 1];
        } else {
            if (b[-x - 1] == -2e9) return false;
            sw[-x - 1] = false;
            x = b[-x - 1];
        }
    }
    return true;
}

void create_circuit(int m, vector<int> A) {
    n = (int)A.size();
    c.resize(m + 1);
    for (int i = 0; i < m + 1; i++) c[i] = -2e9;
    n++;
    int bit = ceil(log2(n));
    int sw_size = 1 << bit;
    int left = sw_size - n;
    vector<pair<int, int>> sw_cnt, nsw_cnt;
    sw_cnt.push_back({ 0, -1 });
    for (int t = bit - 1; t >= 0; t--) {
        bool rem = false;
        if (left >= 1 << t) {
            left -= 1 << t;
            rem = true;
        }
        nsw_cnt.clear();
        for (int i = 0; i < (int)sw_cnt.size(); i++) {
            if (sw_cnt[i].second == -1) c[sw_cnt[i].first] = -s - 1;
            else if (sw_cnt[i].second == 0) a[sw_cnt[i].first] = -s - 1;
            else b[sw_cnt[i].first] = -s - 1;
            if (rem) {
                nsw_cnt.push_back({ s, 1 });
                a.push_back(-1);
                b.push_back(-2e9);
                rem = false;
            } else {
                nsw_cnt.push_back({ s, 0 });
                nsw_cnt.push_back({ s, 1 });
                a.push_back(-2e9);
                b.push_back(-2e9);
            }
            s++;
        }
        sw_cnt = nsw_cnt;
    }
    for (int i = 0; i <= m; i++) c[i] = -1;
    n--;
    A.push_back(0);
    int curr = 0;
    for (int i = 0; i <= n; i++) {
        while (goForward(curr)) ;
        if (curr >= 0) c[curr] = A[i];
        else if (!sw[-curr - 1]) {
            a[-curr - 1] = A[i];
            sw[-curr - 1] = true;
        } else {
            b[-curr - 1] = A[i];
            sw[-curr - 1] = false;
        }
        curr = A[i];
    }
    answer(c, a, b);
}

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