Submission #75888

#	Time	Username	Problem	Language	Result	Execution time	Memory
75888		kdh9949	Mechanical Doll (IOI18_doll)	C++17	100 / 100	207 ms	10616 KiB

doll

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

static int n, m, q, v;
static vector<int> a, c, x, y, l, s;

void f(int z){
    x.push_back(-1);
    y.push_back(-1);
    l.push_back(!z);
    s.push_back(0);
    if(!z) return;
    int w = q;
    x[w - 1] = -(++q);
    f(z - 1);
    y[w - 1] = -(++q);
    f(z - 1);
}

void create_circuit(int M, vector<int> A) {
    n = A.size(); m = M; a = A;
    c = vector<int>(m + 1, -1);
    for(v = 1; (1 << (v - 1)) <= n; v++){
        x.push_back(-1);
        y.push_back(-(v + 1));
        l.push_back(0);
        s.push_back(0);
    }
    y[--v - 1] = 0;
    q = v;
    for(int i = v, j = 0; i >= 1; i--, j++){
        if(n & (1 << j)){
            if(!j) x[i - 1] = 1;
            else{
                x[i - 1] = -(++q);
                f(j - 1);
            }
        }
    }
    q = 0;
    for(int z = 1; z; ){
        s[z - 1] ^= 1;
        if(s[z - 1]){
            if(l[z - 1]){
                x[z - 1] = a[q++];
                z = 1;
            }
            else if(x[z - 1] == 1){
                x[z - 1] = a[q++];
                z = 1;
            }
            else z = -x[z - 1];
        }
        else{
            if(l[z - 1]){
                y[z - 1] = a[q++];
                z = 1;
            }
            else z = -y[z - 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