Submission #829807

#	Time	Username	Problem	Language	Result	Execution time	Memory
829807		vnm06	Mechanical Doll (IOI18_doll)	C++14	100 / 100	91 ms	11028 KiB

doll

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

bool st2(int n)
{
    return n==(n&(-n));
}

vector<int> C, D;
vector<int> X, Y;

int brn=0;
int ty[1000005];
void dfs(int pos)
{
    while(1)
    {
        ///cout<<pos<<endl;
    if(pos>=0) pos=C[pos];
    else
    {
        if(brn==D.size()) return;
        ty[-pos-1]^=1;
        if(ty[-pos-1]==1)
        {
            if(!X[-pos-1])
            {
                X[-pos-1]=D[brn];
                pos=D[brn];
                brn++;
            }
            else pos=X[-pos-1];
        }
        else
        {
            if(!Y[-pos-1])
            {
                Y[-pos-1]=D[brn];
                pos=D[brn];
                brn++;
            }
            else pos=Y[-pos-1];
        }
    }
    }
}


void create_circuit(int M, std::vector<int> A)
{
    C.resize(M+1);
    D=A;
    for (int i = 0; i <= M; ++i) C[i]=-1;
    int N = A.size();
    int brb=1, n2=N;
    while(n2!=1)
    {
        brb++;
        n2/=2;
    }
    ///cout<<brb<<endl;
    X.resize(N+brb);
    Y.resize(N+brb);
    int tpos=brb+1;
    for(int i=0; i<brb-1; i++)
    {
        int st2=(1<<(brb-i-1));
        ///cout<<st2<<"  ";
        ///cout<<tpos<<endl;
        if(st2&N)
        {
            X[i]=-tpos;
            Y[i]=-i-2;
            for(int j=tpos; j<tpos+st2/2-1; j++)
            {
                X[j-1]=-(2*(j-tpos+1)+tpos-1);
                Y[j-1]=-(2*(j-tpos+1)+tpos);
            }
            tpos+=st2-1;
        }
        else
        {
            X[i]=-1;
            Y[i]=-i-2;
        }
    }
    if(N%2==0) {X[brb-1]=-1;}
    Y[brb-1]=0;
    dfs(0);
    X.resize(tpos-1);
    Y.resize(tpos-1);
    ///for(int i=0; i<X.size(); i++) cout<<X[i]<<" "<<Y[i]<<endl;
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void dfs(int)':
doll.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(brn==D.size()) return;
      |            ~~~^~~~~~~~~~

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