Submission #464016

#	Time	Username	Problem	Language	Result	Execution time	Memory
464016		tomsyd	Mechanical Doll (IOI18_doll)	C++17	37 / 100	118 ms	12996 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;

const int inf = 1e9;

int rev(int node, int nb){
	int ans = 0;
	for (int i=0; i<nb; ++i){
		if (node&(1<<i)){
			ans += (1<<(nb-1-i));
		}
	}
	return ans;
}

void create_circuit(int M, vector<int> bisA) {
	deque<int> A;
	for (int i:bisA) A.emplace_back(i);
	int pow2 = 1, N = A.size();
   vector<int> C(M+1,-1);
	if(N == 1){
		C = vector<int>(M+1);
		vector<int> da,db;
		C[0] = A[0];
		C[A[0]] = 0;
		answer(C,da,db);
      return;
   }
	int nb = 0;
	while (pow2 < N+1){
		nb++;
		pow2 *= 2;
	}
	A.emplace_back(0);
	while (A.size() < pow2) A.emplace_front(-1);
	pow2 /= 2;
	vector<int> X(2*pow2-1,-1),Y(2*pow2-1,-1);
	for (int i=0; i<pow2-1; ++i){
		X[i] = -(2*(i+1));
		Y[i] = -(2*(i+1)+1);
	}
/*	cout << "A : ";
	for (int i:A) cout << i << ' ';
	cout << endl;
*/	for(int idx=pow2-1, id = 0; idx<X.size(); ++idx, ++id){
		X[idx] = A[rev(2*id,nb)];
		Y[idx] = A[rev(2*id+1,nb)];
		if (X[idx] == -1 and Y[idx] == -1){
			X[idx/2] = X[idx];
			Y[idx/2] = Y[idx];
			X[idx] = -inf;
			Y[idx] = -inf;
		}
	}
/*	for (int i=0; i<X.size(); ++i){
		cout << -i-1 << " : " << X[i] << ' ' << Y[i] << endl;
	}
*/
	vector<int> newx,newy;
	for (int i=0; i<X.size(); ++i){
		if (X[i] != -inf){
			newx.emplace_back(X[i]);
			newy.emplace_back(Y[i]);
		}
	}
	answer(C,newx,newy);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:36:18: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  while (A.size() < pow2) A.emplace_front(-1);
      |         ~~~~~~~~~^~~~~~
doll.cpp:46:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 | */ for(int idx=pow2-1, id = 0; idx<X.size(); ++idx, ++id){
      |                                ~~~^~~~~~~~~
doll.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i=0; i<X.size(); ++i){
      |                ~^~~~~~~~~

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