Submission #362884

#	Time	Username	Problem	Language	Result	Execution time	Memory
362884		benedict0724	Mechanical Doll (IOI18_doll)	C++17	100 / 100	142 ms	13072 KiB

doll

#include "doll.h"
#include <queue>
#include <stdio.h>

int x[400002], y[400002];

void change(int M, std::vector<int> &C, std::vector<int> &X, std::vector<int> &Y, std::vector<int> A){
    std::queue<int> q;
    A.push_back(0);
    int L = (int)A.size();

    for(int i=0;i<=M;i++) C[i] = -1;

    for(int i=0;i<=400000;i++){
        x[i] = 1;
        y[i] = 1;
    }

    int h = 0;
    while((1<<h) < L) h++;
    L = (1<<h) - L;

    q.push(1);

    int cnt = 1;

    for(int i=h-1;i>=0;i--){
        std::queue<int> temp;
        int now = q.front(); q.pop();
        if(i == 0 && (1&L)){
            x[now] = -1;
        }
        if(i == 0) break;

        if((1<<i) & L){
            x[now] = -1;
            ++cnt; y[now] = -cnt; temp.push(cnt);
        }
        else{
            ++cnt; x[now] = -cnt; temp.push(cnt);
            ++cnt; y[now] = -cnt; temp.push(cnt);
        }
        while(!q.empty()){
            int now = q.front(); q.pop();
            ++cnt; x[now] = -cnt; temp.push(cnt);
            ++cnt; y[now] = -cnt; temp.push(cnt);
        }
        while(!temp.empty()){
            int now = temp.front(); temp.pop();
            q.push(now);
        }
    }

    std::vector<bool> visited(cnt);
    X.resize(cnt); Y.resize(cnt);

    for(int i=0;i<cnt;i++){
        X[i] = x[i+1];
        Y[i] = y[i+1];
    }

    for(int i=0;i<(1<<h) - L;i++){
        int curr = -1;
        for(;;){
            if(!visited[-curr-1]){
                visited[-curr-1] = true;
                if(x[-curr] == 1) { X[-curr-1] = A[i]; break; }
                else curr = x[-curr];
            }
            else{
                visited[-curr-1] = false;
                if(y[-curr] == 1) { Y[-curr-1] = A[i]; break; }
                else curr = y[-curr];
            }
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    std::vector<int> C(M + 1);
    std::vector<int> X, Y;
    change(M, C, X, Y, A);
    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