Submission #525719

#	Time	Username	Problem	Language	Result	Execution time	Memory
525719		byunjaewoo	Mechanical Doll (IOI18_doll)	C++17	0 / 100	3 ms	4940 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int Nmax=200010;
int M, N, cnt, Size, A[Nmax];
int out[Nmax], X[2*Nmax], Y[2*Nmax];
bool st[Nmax];
vector<int> V[Nmax];

void DFS(int curr, int s, int e) {
    if(e-s==1) {
        X[-curr]=Y[-curr]=INT_MAX;
        if(s<=Size-N) X[-curr]=-1;
        return;
    }
    int m=(s+e)/2;
    if(m<=Size-N) X[-curr]=-1;
    else {
        X[-curr]=--cnt;
        DFS(X[-curr], s, m);
    }
    Y[-curr]=--cnt;
    DFS(Y[-curr], m+1, e);
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    N=A.size();
    Size=(1<<(32-__builtin_clz(N-1)));
    out[0]=--cnt;
    DFS(out[0], 1, Size);
    for(int i=1; i<=N; i++) {
        for(int curr=-1; ; ) {
            st[-curr]^=1;
            if(!st[-curr]) {
                if(Y[-curr]==INT_MAX) {
                    Y[-curr]=A[i-1];
                    break;
                }
                curr=Y[-curr];
            }
            else {
                if(X[-curr]==INT_MAX) {
                    X[-curr]=A[i-1];
                    break;
                }
                curr=X[-curr];
            }
        }
    }
    vector<int> C, l, r;
    for(int i=0; i<=M; i++) C.push_back(out[i]);
    for(int i=1; i<=-cnt; i++) {
        l.push_back(X[i]); r.push_back(Y[i]);
    }
    answer(C, l, r);
}

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