Submission #856282

#	Time	Username	Problem	Language	Result	Execution time	Memory
856282		sunwukong123	Mechanical Doll (IOI18_doll)	C++14	37 / 100	99 ms	14680 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 dnc(int st, int en){

    int mi=(st+en)/2;
   
    int idx=cur--;
    if(st+1==en){
        if(st>=n)X[-idx]=-1;
        if(en>=n)Y[-idx]=-1;
        return idx;
    } else{
        X[-idx]=dnc(st,mi);
        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();
    if(n==0){
        // do something.
        exit(0);
    }

    k=msb(n);

    dnc(0,k-1);
    Y[-(cur+1)]=0;

    C[0]=-1; // go to the first thing that i need to go
    trav(-1,A[0]);
    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);
    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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56