Submission #284482

#	Time	Username	Problem	Language	Result	Execution time	Memory
284482		MKopchev	Mechanical Doll (IOI18_doll)	C++14	37 / 100	220 ms	10248 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++;

    while(n+1<(1<<k))
    {
        A.push_back(-1);
        n++;
    }

    A.push_back(0);
    n++;

    //for(auto k:A)cout<<k<<" ";cout<<endl;

    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=0;i<X.size();i++)
        assert(type[i]==0);

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

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

    answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i=0;i<X.size();i++)
      |                 ~^~~~~~~~~

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