Submission #169857

#	Time	Username	Problem	Language	Result	Execution time	Memory
169857		dennisstar	Mechanical Doll (IOI18_doll)	C++11	100 / 100	130 ms	13724 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;

int N, M, l;
vim A;
int dep[(1<<20)], chk[(1<<20)], val[(1<<20)], cnt[(1<<20)], num[(1<<20)];
vim C, X, Y;

void dfs(int v) {
	for (int i=1; ; ) {
		if (chk[i]) {i=1; continue;}
		if ((1<<(l-1))<=i) {val[i]=v; return ;}
		if (cnt[i]==0) {
			cnt[i]=1-cnt[i];
			i=i*2;
			continue;
		}
		if (cnt[i]==1) {
			cnt[i]=1-cnt[i];
			i=i*2+1;
			continue;
		}
	}
}

void create_circuit(int M_, vim A_) {
	A=A_; N=A.size(); M=M_;
	A.push_back(0); N++;
	for (l=0; (1<<l)<N; l++) {}
	l++;
	for (int i=(1<<(l-1)); i<(1<<l)-N; i++) chk[i]=1;
	for (int i=(1<<(l-1))-1; i; i--) {if (chk[i*2]&&chk[i*2+1]) chk[i]=1;}
	for (int i:A) dfs(i);
	for (int i=1; i<(1<<(l-1)); i++) if (cnt[i]) assert(false);
	int cnt=-1;
	for (int i=1; i<(1<<(l-1)); i++) {
		if (chk[i]) continue;
		num[i]=cnt--;
	}
	for (int i=0; i<=M; i++) C.push_back(-1);
	for (int i=1; i<(1<<(l-1)); i++) {
		if (chk[i]) continue;
		if (-num[i]!=X.size()+1) assert(false);
		
		if (chk[i*2]) X.push_back(-1);
		else if (i*2>=(1<<(l-1))) X.push_back(val[i*2]);
		else X.push_back(num[i*2]);

		if (chk[i*2+1]) assert(false);
		else if (i*2+1>=(1<<(l-1))) Y.push_back(val[i*2+1]);
		else Y.push_back(num[i*2+1]);
	}
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, vim)':
doll.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if (-num[i]!=X.size()+1) assert(false);
      |       ~~~~~~~^~~~~~~~~~~~

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