Submission #169854

#	Time	Username	Problem	Language	Result	Execution time	Memory
169854		dennisstar	Mechanical Doll (IOI18_doll)	C++11	84 / 100	135 ms	13076 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);
	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 dfs(int)':
doll.cpp:21:12: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   21 |   if ((1<<l-1)<=i) {val[i]=v; return ;}
      |           ~^~
doll.cpp: In function 'void create_circuit(int, vim)':
doll.cpp:40:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |  for (int i=(1<<l-1); i<(1<<l)-N; i++) chk[i]=1;
      |                 ~^~
doll.cpp:41:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   41 |  for (int i=(1<<l-1)-1; i; i--) {if (chk[i*2]&&chk[i*2+1]) chk[i]=1;}
      |                 ~^~
doll.cpp:44:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |  for (int i=1; i<(1<<l-1); i++) {
      |                      ~^~
doll.cpp:49:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |  for (int i=1; i<(1<<l-1); i++) {
      |                      ~^~
doll.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   if (-num[i]!=X.size()+1) assert(false);
      |       ~~~~~~~^~~~~~~~~~~~
doll.cpp:54:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |   else if (i*2>=(1<<l-1)) X.push_back(val[i*2]);
      |                     ~^~
doll.cpp:58:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   58 |   else if (i*2+1>=(1<<l-1)) Y.push_back(val[i*2+1]);
      |                       ~^~

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