Submission #169851

#	Time	Username	Problem	Language	Result	Execution time	Memory
169851		dennisstar	Mechanical Doll (IOI18_doll)	C++11	84 / 100	106 ms	13084 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<<19)], chk[(1<<19)], val[(1<<19)], cnt[(1<<19)], num[(1<<19)];
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;
		}
		else {
			cnt[i]=1-cnt[i];
			i=i*2+1;
		}
	}
}

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=1; i<(1<<l); i++) if (chk[i/2]) chk[i]=2;
	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 (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:38:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |  for (int i=(1<<l-1); i<(1<<l)-N; i++) chk[i]=1;
      |                 ~^~
doll.cpp:39:18: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |  for (int i=(1<<l-1)-1; i; i--) if (chk[i*2]&&chk[i*2+1]) chk[i]=1;
      |                 ~^~
doll.cpp:43:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   43 |  for (int i=1; i<(1<<l-1); i++) {
      |                      ~^~
doll.cpp:48:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |  for (int i=1; i<(1<<l-1); i++) {
      |                      ~^~
doll.cpp:51:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   51 |   else if (i*2>=(1<<l-1)) X.push_back(val[i*2]);
      |                     ~^~
doll.cpp:54:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |   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