Submission #294927

#	Time	Username	Problem	Language	Result	Execution time	Memory
294927		kshitij_sodani	Mechanical Doll (IOI18_doll)	C++14	53 / 100	188 ms	26132 KiB

doll

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
#define mp make_pair
typedef long long llo;

#include "doll.h"
vector<int> pre[100001];
//vector<int> adj[100001];
vector<int> ac;
vector<int> x;
vector<int> y;
int cur=0;
int cot;
pair<int,int> adj[1000001];
int stt[1000001];
void con(int ind,int tot,int dd){
//	x.pb(0);
	//y.pb(0);
	//cout<<dd<<".."<<endl;
	if(ind==tot-1){
		x.pb(0);
		y.pb(0);
	}
	else{
		adj[-dd]={-cur+1,-cur+2};
		//cout<<-dd<<":"<<-cur+1<<" "<<-cur+2<<endl;
		/*if(-dd-1==3){
			cout<<11<<endl;
			
		}*/
		//cout<<x.size()<<endl;
		x[-dd-1]=cur-1;
		y[-dd-1]=cur-2;
		x.pb(0);
		x.pb(0);
		y.pb(0);
		y.pb(0);
		
		//cout<<-dd-1<<endl<<"::"<<cur-1<<endl;
	//	cout<<x[3]<<endl;
		cur--;
		cur--;
		int ba=cur;
		con(ind+1,tot,cur+1);
		con(ind+1,tot,ba);
	}
}
void create_circuit(int m, vector<int> aa) {
	int n=aa.size();
	
	for(int i=0;i<=m;i++){
		ac.pb(0);
	}
	ac[0]=aa[0];
	for(int i=0;i<aa.size()-1;i++){
		pre[aa[i]].pb(aa[i+1]);
	}
	pre[aa.back()].pb(0);
	
	for(int i=1;i<=m;i++){
		cot=i;
		if(pre[i].size()==0){
			continue;
		}
		if(pre[i].size()==1){
			ac[i]=pre[i][0];
		}
		else{
			int xx=pre[i].size();
			int dep=0;
			for(int j=0;j<=19;j++){
				if((1<<j)>=xx){
					dep=j;
					break;
				}
			}
		//	cout<<dep<<endl;
			cur--;
			ac[i]=cur;
			x.pb(0);
			y.pb(0);
			con(0,dep,cur);
		//	continue;
			int op=(1<<dep);
			int ind2=0;
			//continue;
			for(int j=0;j<(1<<dep);j++){
				int st=-ac[i];
				//cout<<j<<",,"<<endl;
				for(int jj=0;jj<dep-1;jj++){
					if(stt[st]==0){
						stt[st]=1-stt[st];
						st=adj[st].a;
					}
					else{
						stt[st]=1-stt[st];
						st=adj[st].b;
					}
					
				}
				op--;
				//cout<<j<<":"<<st<<endl;
				if(op<pre[i].size()){
					//cout<<stt[st]<<",,"<<pre[i][ind2]<<endl;
					if(stt[st]==0){
						x[st-1]=pre[i][ind2];
					}
					else{
						y[st-1]=pre[i][ind2];
					}
					stt[st]=1-stt[st];
					ind2++;
				}
				else{
					if(stt[st]==0){
						x[st-1]=ac[i];
					}
					else{
						y[st-1]=ac[i];
					}
					stt[st]=1-stt[st];
				}
			}
		}
		/*else if(pre[i].size()==2){
			cur--;
			ac[i]=cur;
			x.pb(pre[i][0]);
			y.pb(pre[i][1]);
		}
		else if(pre[i].size()==3){
			cur--;
			ac[i]=cur;
			x.pb(cur-1);
			y.pb(cur-2);
			cur--;
			x.pb(pre[i][0]);
			y.pb(cur+1);
			cur--;
			x.pb(pre[i][1]);
			y.pb(pre[i][2]);
		}
		else if(pre[i].size()==4){
			cur--;
			ac[i]=cur;
			x.pb(cur-1);
			y.pb(cur-2);
			cur--;
			x.pb(pre[i][0]);
			y.pb(pre[i][2]);
			cur--;
			x.pb(pre[i][1]);
			y.pb(pre[i][3]);
		}*/
	}
	/*if(x.size()>2*n){
		while(true){
			continue;
		}
	}*/
	while(x.size()>-cur){
		x.pop_back();
	}
	while(y.size()>-cur){
		y.pop_back();
	}
	/*for(auto j:ac){
		cout<<j<<",";
	}
	cout<<endl;
	for(auto j:x){
		cout<<j<<",";
	}
	cout<<endl;
	for(auto j:y){
		cout<<j<<",";
	}
	cout<<endl;*/

	answer(ac,x,y);









}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<aa.size()-1;i++){
      |              ~^~~~~~~~~~~~
doll.cpp:106:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     if(op<pre[i].size()){
      |        ~~^~~~~~~~~~~~~~
doll.cpp:164:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  164 |  while(x.size()>-cur){
      |        ~~~~~~~~^~~~~
doll.cpp:167:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  167 |  while(y.size()>-cur){
      |        ~~~~~~~~^~~~~
doll.cpp:52:6: warning: unused variable 'n' [-Wunused-variable]
   52 |  int n=aa.size();
      |      ^

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