Submission #784803

#	Time	Username	Problem	Language	Result	Execution time	Memory
784803		QwertyPi	Mechanical Doll (IOI18_doll)	C++14	10 / 100	1081 ms	20680 KiB

doll

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

const int SLOT = 1234567;
using namespace std; 

int S = 0;
map<int, int> MX, MY; 
map<int, bool> T;
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(auto& [a, b] : MX) if(b == 0) b = root;
  for(auto& [a, b] : MY) if(b == 0) b = root;
  for(auto i : MX) T[i.first] = 0;
  int cur = 0, filled = 0;
  while(filled < N){
  	if(cur >= 0) cur = C[cur];
	  else {
  		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(MX.size()), Y(MY.size());
  for (int k = 0; k < MX.size(); ++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:13:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   13 |  int sr = min(n, 1 << lv - 1), sl = n - sr;
      |                       ~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:32:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |   for(auto& [a, b] : MX) if(b == 0) b = root;
      |             ^
doll.cpp:33:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for(auto& [a, b] : MY) if(b == 0) b = root;
      |             ^
doll.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int k = 0; k < MX.size(); ++k) {
      |                   ~~^~~~~~~~~~~

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