제출 #856567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856567		sunwukong123	자동 인형 (IOI18_doll)	C++14	100 / 100	80 ms	15524 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 400005;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int k;
int n;
int msb(unsigned int n){
  return 1<<(32-__builtin_clz(n));
}
int cur=-1;
int X[MAXN], Y[MAXN], C[MAXN];
bool state[MAXN];
int I[MAXN];
int lim;
int dnc(int st, int en){

    int mi=(st+en)/2;
   
    int idx=cur--;
    if(st+1==en){
        if(!(st>lim)){
             X[-idx]=-1;
        } else{
            
        }

        return idx;
    } else{
        
        
        if(mi>lim){
            X[-idx]=dnc(st,mi);
        } else{
            X[-idx]=-1;
        }
        Y[-idx]=dnc(mi+1,en);
        return idx;
    }
    
}
void trav(int x, int next){

    if(state[-x]==0){
        state[-x]=!state[-x];
        if(X[-x]){
            trav(X[-x],next);
        } else{
            X[-x]=next;
        }

    } else{
        state[-x]=!state[-x];
        if(Y[-x]){
            trav(Y[-x],next);
        } else{
            Y[-x]=next;
        }
    }
}
void create_circuit(int M, vector<int> A) {

    n=A.size();

    k=msb(n);
    lim=k-n-1;


    dnc(0,k-1);

    C[0]=-1; // go to the first thing that i need to go
    for(int i=0;i<n;i++){
        C[A[i]]=-1;
        if(i==n-1)trav(-1,0);
        else trav(-1,A[i+1]);
    }
    
    vector<int> AA,AB,AC;
    AA=vector<int>(M+1,-1);
    AA[0]=A[0];
    int S=-cur;--S;
    AB=vector<int>(S);AC=vector<int>(S);
    for(int i=0;i<S;i++){
        AB[i]=X[i+1];
        AC[i]=Y[i+1];
    }

    answer(AA,AB,AC);
}

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