Submission #284476

#	Time	Username	Problem	Language	Result	Execution time	Memory
284476		MKopchev	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	204 KiB

doll

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

const int nmax=1e6+42;

int n;

vector<int> X,Y;

int pointer=0;

int stop;

bool type[nmax];

void push(int node,int val)
{
    //cout<<"push "<<node<<" "<<val<<endl;

    if(node<stop)
    {
        int to=-X[node];

        if(type[node]==1)to=-Y[node];

        type[node]=!type[node];

        push(to,val);
        return;
    }
    else
    {
        if(type[node]==0)X[node]=val;
        else Y[node]=val;

        type[node]=!type[node];
        return;
    }
}
/*
void answer(vector<int> c,vector<int> x,vector<int> y)
{
    cout<<c.size()<<" "<<x.size()<<" "<<y.size()<<endl;

    cout<<"c: ";for(auto k:c)cout<<k<<" ";cout<<endl;
    cout<<"x: ";for(auto k:x)cout<<k<<" ";cout<<endl;
    cout<<"y: ";for(auto k:y)cout<<k<<" ";cout<<endl;
}
*/
void create_circuit(int M, std::vector<int> A)
{
    n=A.size();

    vector<int> C={};

    for(int j=0;j<=M;j++)
        C.push_back(-1);

    int k=1;

    while((1<<k)<n+1)k++;

    stop=(1<<(k-1));

    for(int i=0;i<(1<<k);i++)
    {
        X.push_back(-1);
        Y.push_back(-1);
    }

    for(int i=1;i<(1<<(k-1));i++)
    {
        X[i]=-(2*i);
        Y[i]=-(2*i+1);
    }

    for(int i=0;i<n;i++)
    {
        push(1,A[i]);
    }

    for(int i=(1<<(k-1));i<(1<<k);i++)
    {
        if(X[i]!=-1&&Y[i]!=-1)continue;

        if(X[i]!=-1)
        {
            swap(X[i],Y[i]);
            X[i]=-i;
        }
        else
        {
            X[i]=-i;
        }
    }

    X.erase(X.begin(),X.begin()+1);

    Y.erase(Y.begin(),Y.begin()+1);

    answer(C,X,Y);
}

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