Submission #301532

#	Time	Username	Problem	Language	Result	Execution time	Memory
301532		TMJN	Mechanical Doll (IOI18_doll)	C++17	53 / 100	205 ms	16512 KiB

doll

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

int c;
vector<int>K;
vector<int>X,Y,C;
vector<vector<int>>P;

int dfs(int num,int dep,vector<int>&v){
	if(num+(1<<dep)>=v.size()){
		return v[num];
	}
	else{
		int t=c;
		c++;
		int x=dfs(num,dep+1,v);
		int y=dfs(num+(1<<dep),dep+1,v);
		if(x==0xE869120&&y==0xE869120){
			c--;
			return 0xE869120;
		}
		X[t]=x;
		Y[t]=y;
		return -t-1;
	}
}

void create_circuit(int M,vector<int>A){
	c=0;
	K=A;
	K.push_back(0);
	reverse(K.begin(),K.end());
	K.push_back(0);
	reverse(K.begin(),K.end());
	P=vector<vector<int>>(M+1);
	C=vector<int>(M+1,0);
	X=Y=vector<int>(A.size()*2,0xE869120);
	for(int i=0;i<K.size()-1;i++){
		P[K[i]].push_back(K[i+1]);
	}
	for(int i=0;i<=M;i++){
		if(P[i].empty())continue;
		for(int j=0;;j++){
			if(P[i].size()<=(1<<j)){
				while(P[i].size()<(1<<j))P[i].push_back(0xE869120);
				for(int j=P[i].size()-1;;j--){
					if(P[i][j]!=0xE869120){
						swap(P[i][j],P[i].back());
						break;
					}
				}
				int l,r;
				l=c;
				C[i]=dfs(0,0,P[i]);
				r=c;
				for(int k=l;k<r;k++){
					if(X[k]==0xE869120){
						X[k]=C[i];
					}
					if(Y[k]==0xE869120){
						Y[k]=C[i];
					}
				}
				break;
			}
		}
	}
	while(!X.empty()&&X.back()==0xE869120){
		X.pop_back();
		Y.pop_back();
	}
	vector<bool>B(400000,false);
	int p=0;
	vector<int>T;
	int cnt=0;
	do{
		cnt++;
		if(p>=0){
			if(p)T.push_back(p);
			p=C[p];
		}
		else{
			if(B[-p-1]){
				B[-p-1]=!B[-p-1];
				p=Y[-p-1];
			}
			else{
				B[-p-1]=!B[-p-1];
				p=X[-p-1];
			}
		}
	}while(p);
	assert(A==T);
	bool f=false;
	for(int i=0;i<400000;i++){
		f|=B[i];
	}
	assert(!f);
	for(int i:C){
		assert(-(int)X.size()<=i&&i<=M);
	}
	for(int i:X){
		assert(-(int)X.size()<=i&&i<=M);
	}
	for(int i:Y){
		assert(-(int)X.size()<=i&&i<=M);
	}
	assert(cnt<=20000000);
	answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'int dfs(int, int, std::vector<int>&)':
doll.cpp:11:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  if(num+(1<<dep)>=v.size()){
      |     ~~~~~~~~~~~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<K.size()-1;i++){
      |              ~^~~~~~~~~~~
doll.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |    if(P[i].size()<=(1<<j)){
      |       ~~~~~~~~~~~^~~~~~~~
doll.cpp:46:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |     while(P[i].size()<(1<<j))P[i].push_back(0xE869120);
      |           ~~~~~~~~~~~^~~~~~~

• 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