Submission #995448

#	Time	Username	Problem	Language	Result	Execution time	Memory
995448		hirayuu_oj	Mechanical Doll (IOI18_doll)	C++17	100 / 100	103 ms	12116 KiB

doll

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
ll LINF=(1LL<<61)-1;
ll MINF=1LL<<40;
int INF=INT_MAX>>1;

#include "doll.h"

template<class S>
void out_vector(vector<S> v){
    for(S i:v)cerr<<i<<" ";
    cerr<<"\n";
}

vector<int> X,Y;
int make(int x,int y){
    if(y==0)return -1;
    if(x==1)return 0;
    X.emplace_back(0);
    Y.emplace_back(0);
    int ret=X.size();
    int ri=make(x/2,min(y,x/2));
    int lf=make(x/2,max(0,y-x/2));
    X[ret-1]=lf;
    Y[ret-1]=ri;
    return -ret;
}
void create_circuit(int M, std::vector<int> A) {
    int N=A.size();
    A.emplace_back(0);
    vector<int> C(M+1,-1);
    C[0]=A[0];
    int ceil=1;
    while(ceil<N)ceil<<=1;
    make(ceil,N);
    if(N==1){
        X={-1};
        Y={0};
    }
    int S=X.size();
    vector<int> cond(S,0);
    vector<pair<int,int>> order;
    rep(i,N){
        int pos=-1;
        while(true){
            if(cond[-pos-1]==0){
                cond[-pos-1]=1;
                if(X[-pos-1]==0){
                    order.emplace_back(pos,0);
                    break;
                }
                else{
                    pos=X[-pos-1];
                }
            }
            else{
                cond[-pos-1]=0;
                if(Y[-pos-1]==0){
                    order.emplace_back(pos,1);
                    break;
                }
                else{
                    pos=Y[-pos-1];
                }
            }
        }
    }
    rep(i,N){
        if(order[i].second==0){
            X[-order[i].first-1]=A[i+1];
        }
        else{
            Y[-order[i].first-1]=A[i+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