Submission #292724

#	Time	Username	Problem	Language	Result	Execution time	Memory
292724		Hideo	Mechanical Doll (IOI18_doll)	C++17	100 / 100	136 ms	15648 KiB

doll

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

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pi pair < int, int >
#define vi vector < int >
#define pb push_back

const int MAXN = 4e5 + 7;
const int con = 3e7 + 7;

vi a, C, X, Y;
int n, sz, t, c;

struct sw{
    int x, y, nxt;
    sw(){
        x = y = nxt = 0;
    }
} s[MAXN];

void build (int v, int l, int r){
    if (l + 1 == r){
        if (sz - l + 1 > n)
            s[v].x = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (sz - mid + 1 <= n){
        s[v].x = ++t;
        build(t, l, mid);
    }
    else
        s[v].x = 1;
    s[v].y = ++t;
    build(t, mid + 1, r);
}

void reshuffle (int v){
    if (!s[v].nxt){
        s[v].nxt = 1;
        if (s[v].x)
            reshuffle(s[v].x);
        else {
            s[v].x = con + a[++c];
            if (a[c] == 0)
                assert(false);
            reshuffle(1);
        }
    }
    else {
        s[v].nxt = 0;
        if (s[v].y)
            reshuffle(s[v].y);
        else {
            s[v].y = con + a[++c];
            if (a[c] == 0)
                return;
            reshuffle(1);
        }
    }
}

void create_circuit(int M, vector <int> A) {
    a = A;
    n = a.size();
    if (n == 1){
        C.pb(a[0]);
        C.pb(0);
        answer(C, X, Y);
        return;
    }
    t = 1;
    a.pb(0);
    sz = (1 << int(ceil(log2(n))));
    build(1, 1, sz);
    reshuffle(1);
    for (int i = 1; i <= t; i++){
        if (s[i].x < con)
            X.pb(-s[i].x);
        else
            X.pb(s[i].x - con);
        if (s[i].y < con)
            Y.pb(-s[i].y);
        else
            Y.pb(s[i].y - con);
    }
    C.pb(a[0]);
    for (int i = 1; i <= M; i++)
        C.pb(-1);
    answer(C, X, Y);
}

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