Submission #407082

#	Time	Username	Problem	Language	Result	Execution time	Memory
407082		Antekb	Mechanical Doll (IOI18_doll)	C++14	100 / 100	205 ms	12588 KiB

doll

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

void create_circuit(int M, vector<int> A) {
  	int N = A.size();
  	vector<int> to;
  	if(N==1){
  		vector<int> C(M+1, 0);
  		C[0]=1;
  		answer(C, {}, {});
  		return;
  	}
  	for(int i=0; i<N-1; i++){
  		to.push_back(A[i+1]);
  	}
  	int wsk=-1;
  	vector<int> C(M+1), X, Y;
  	C[0]=A[0];
  	to.push_back(0);
  		int t=1;
  		while(t<to.size())t*=2;
  		vector<int> l(t), r(t), num(t);
  		//cout<<i<<" "<<to[i].size()<<"\n";
  		//for(int j:to[i])cout<<j<<" ";
  		//cout<<"\n";
  		int wsk2=0;
  		for(int j=0; j<t; j++){
  			vector<int> bin;
  			int k=j;
  			while(k>0){
  				bin.push_back(k&1);
  				k>>=1;
  			}
  			bin.resize(__builtin_ctz(t));
  			//reverse(bin.begin(), bin.end());
  			for(int i:bin){
  				k<<=1;
  				k+=i;
  			}
  			//cout<<j<<" "<<k<<"\n";
  			if(k+to.size()>=t && wsk2<to.size()){
  				if(k&1)r[t/2+k/2]=to[wsk2];
  				else l[t/2+k/2]=to[wsk2];
  				wsk2++;
  			}
  			else{
  				if(k&1)r[t/2+k/2]=wsk;
  				else l[t/2+k/2]=wsk;
  			}
  		}
  		//for(int j=0; j<t; j++)cout<<"("<<l[j]<<" "<<r[j]<<") ";
  		//cout<<"\n";
  		vector<int> czy(t);
  		for(int j=t-1; j; j--){
  			if(r[j]==wsk && l[j]==wsk){
  				if(j&1)r[j/2]=l[j];
  				else l[j/2]=l[j];
  				czy[j]=0;
  			}
  			else czy[j]=1;
  		}
  		//for(int j=0; j<t; j++)cout<<czy[j];
  		//cout<<"\n";
  		for(int j=1; j<t; j++)if(czy[j])num[j]=wsk--;
  		for(int j=t-1; j; j--){
  			if(czy[j]){
  				if(j&1)r[j/2]=num[j];
  				else l[j/2]=num[j];
  			}
  		}
  		//for(int j=0; j<t; j++)cout<<"("<<l[j]<<" "<<r[j]<<" "<<num[j]<<") ";
  		//cout<<"\n";
  		X.resize(-wsk-1);
  		Y.resize(-wsk-1);
  		for(int j=1; j<t; j++){
  			if(czy[j]){	
  				X[-1-num[j]]=l[j];
  				Y[-1-num[j]]=r[j];
  			}
  		}
  	for(int i=1; i<=M; i++){
  		C[i]=-1;
  	}
  	/*for(int i:C)cout<<i<<" ";
  	cout<<"\n";
  	for(int i:X)cout<<i<<" ";
  	cout<<"\n";
  	for(int i:Y)cout<<i<<" ";
  	cout<<"\n";*/
  	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:22:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     while(t<to.size())t*=2;
      |           ~^~~~~~~~~~
doll.cpp:42:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |      if(k+to.size()>=t && wsk2<to.size()){
      |         ~~~~~~~~~~~^~~
doll.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |      if(k+to.size()>=t && wsk2<to.size()){
      |                           ~~~~^~~~~~~~~~

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