Submission #120207

#	Time	Username	Problem	Language	Result	Execution time	Memory
120207		dsjong	Mechanical Doll (IOI18_doll)	C++14	18 / 100	113 ms	7476 KiB

doll

//SUBTASK 5
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
bool val[1000005];
int simulate(int N,vector<int>X,vector<int>Y){
	memset(val,0,sizeof val);
	int ans;
	for(int i=1;i<=N;i++){
		int j=1;
		while(j!=0){
			ans=j;
			val[j]^=1;
			if(val[j]) j=X[j-1];
			else j=Y[j-1];
		}
	}
	//cout<<ans<<endl;
	return ans-1;
}
void create_circuit(int M, vector<int> A){
	int N=A.size();
	vector<int>levels;
	vector<int>C;
	C.push_back(1);
	C.push_back(-1);
	int x=N,S=0;
	while(x>1){
		x=(x+1)/2;
		S+=x;
		levels.push_back(x);
	}
	reverse(levels.begin(),levels.end());
	vector<int>X(S),Y(S);
	for(int i=0;i<S;i++){
		X[i]=0;
		Y[i]=0;
	}
	int cur=0,sum=1;
	for(int i=0;i<levels.size()-1;i++){
		if(levels[i+1]==2*levels[i]){
			X[cur]=++sum;
			Y[cur]=++sum;
			cur++;
		}
		else{
			X[cur]=++sum;
			Y[cur]=1;
			cur++;
		}
		for(int j=1;j<=levels[i]-1;j++){
			X[cur]=++sum;
			Y[cur]=++sum;
			cur++;
		}
	}
	int curry=simulate(2*levels.back(),X,Y);
	for(int i=1;i<=levels.back();i++){
		X[cur]=Y[cur]=-1;
		cur++;
	}
	if(N%2==0) X[curry]=-1;
	else X[curry]=1;
	Y[curry]=0;
	for(int i=0;i<S;i++){
		X[i]*=-1;
		Y[i]*=-1;
	}
	answer(C,X,Y);
	/*for(int i:C) cout<<i<<" ";
	cout<<endl;
	for(int i:X) cout<<i<<" ";
	cout<<endl;
	for(int i:Y) cout<<i<<" ";
	cout<<endl;*/
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<levels.size()-1;i++){
      |              ~^~~~~~~~~~~~~~~~
doll.cpp: In function 'int simulate(int, std::vector<int>, std::vector<int>)':
doll.cpp:19:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   19 |  return ans-1;
      |             ^

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