제출 #1227688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227688		Hamed_Ghaffari	Mechanical Doll (IOI18_doll)	C++20	100 / 100	89 ms	10468 KiB

doll

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

int N=-1, M;
vector<int> X, Y;
vector<bool> st;

int build(int n, int x) {
    if(x==n) return -1;
    if(n==1) return M+1;
    int v = N--;
    X.push_back(M+1);
    Y.push_back(M+1);
    int t = min(x, n/2);
    X[-v-1] = build(n/2, t);
    Y[-v-1] = build(n/2, x-t);
    return v;
}

void create_circuit(int M, vector<int> A) {
    ::M = M;
    vector<int> C(M+1, 0);
    C[0] = A[0];
    A.push_back(0);
    A = vector<int>(A.begin()+1, A.end());
    int n2 = ((1<<__lg(A.size()))!=A.size()) ? (1<<(__lg(A.size())+1)) : A.size();
    fill(C.begin()+1, C.end(), build(n2, n2-A.size()));
    st = vector<bool>(-N-1, 0);
    int ptr=0;
    for(int v=C[0]; v;) {
        if(v>0) {
            if(C[v]==M+1) C[v] = A[ptr++];
            v = C[v];
        }
        else if(st[-v-1]==0) {
            if(X[-v-1]==M+1) X[-v-1] = A[ptr++];
            st[-v-1] = 1;
            v = X[-v-1];
        }
        else {
            if(Y[-v-1]==M+1) Y[-v-1] = A[ptr++];
            st[-v-1] = 0;
            v = Y[-v-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