Submission #784808

#	Time	Username	Problem	Language	Result	Execution time	Memory
784808		QwertyPi	Mechanical Doll (IOI18_doll)	C++14	100 / 100	93 ms	13668 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

const int SLOT = 1234567;
const int MAXN = 2e5 + 1111;
using namespace std; 

int S = 0;
int MX[MAXN], MY[MAXN]; 
bool T[MAXN];
int build(int lv, int n){
	if(n == 0) return 0;
	if(lv == 0) return SLOT;
	int sr = min(n, 1 << lv - 1), sl = n - sr; 
	int vl = build(lv - 1, sl);
	int vr = build(lv - 1, sr);
	int v = --S;
	MX[-v] = vl, MY[-v] = vr;
	return v;
}

void create_circuit(int M, vector<int> A) {
  A.push_back(0);
  int N = A.size();
  std::vector<int> C(M + 1);
  int level = 0; int x = N; while(x > (1 << level)) level++;
  build(level, N);
  int root = S;
  C[0] = root;
  for (int i = 1; i <= M; ++i) {
    C[i] = root;
  }
  for(int i = 0; i < MAXN; i++) if(MX[i] == 0) MX[i] = root;
  for(int i = 0; i < MAXN; i++) if(MY[i] == 0) MY[i] = root;
  int cur = 0, filled = 0;
  while(filled < N){
  	if(cur >= 0) cur = C[cur];
	  else {
	  	cur = -cur;
  		if(T[cur] && MY[cur] == SLOT) MY[cur] = A[filled++];
  		if(!T[cur] && MX[cur] == SLOT) MX[cur] = A[filled++];
  		int nxt = T[cur] ? MY[cur] : MX[cur]; T[cur] ^= 1;
  		cur = nxt;
	}
  }
  
  std::vector<int> X(-S), Y(-S);
  for (int k = 0; k < -S; ++k) {
  	X[k] = MX[k + 1], Y[k] = MY[k + 1];
  }
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'int build(int, int)':
doll.cpp:14:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   14 |  int sr = min(n, 1 << lv - 1), sl = n - sr;
      |                       ~~~^~~

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