Submission #296584

#	Time	Username	Problem	Language	Result	Execution time	Memory
296584		amiratou	Mechanical Doll (IOI18_doll)	C++14	9 / 100	130 ms	8696 KiB

doll

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

int log_2(int x){
    return 31-__builtin_clz(x);
}
bool state[400005];
int fi;

void create_circuit(int M, vector<int> A) {
	int N = A.size();
    int S=(1<<(log_2(N-1)+1))-1;
    vector<int> C(M + 1),X(S+1),Y(S+1);
    for (int i = 1; i <= S; ++i)
    {
        if((2*i)<=S)X[i]=-i*2;
        else{ 
            X[i]=-i;
            if(!fi)fi=-i;
        }
        if((2*i+1)<=S)Y[i]=-i*2-1;
        else Y[i]=-i;
    }
    C[0]=1,C[1]=-1;
    N--;
    for (int i = 0; i < S+1; ++i)
    {
        int r=-1;
        while(r>fi){
            state[-r]=(!state[-r]);
            if(state[-r])r=X[-r];
            else r=Y[-r];
        }
        //cerr<<r<<"\n";
        if(i<N && i!=S){
            if(!state[-r])X[-r]=1;
            else Y[-r]=1;
        }
        else if(i!=S){
            if(!state[-r])X[-r]=-1;
            else Y[-r]=-1;
        }
        else{
            if(!state[-r])X[-r]=0;
            else Y[-r]=0;
        }
        state[-r]=(!state[-r]);
    }
    /*for (int i = 1; i <= S; ++i)
    {
        cerr<<-i<<" : ";
        cerr<<X[i]<<","<<Y[i]<<"\n";
    }*/
    X.erase(X.begin()),Y.erase(Y.begin());
	answer(C, X, Y);
}

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