Submission #463823

#	Time	Username	Problem	Language	Result	Execution time	Memory
463823		tomsyd	Mechanical Doll (IOI18_doll)	C++17	37 / 100	109 ms	10800 KiB

doll

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

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)];
	}
/*	for (int i=0; i<X.size(); ++i){
		cout << -i-1 << " : " << X[i] << ' ' << Y[i] << endl;
	}
*/	answer(C,X,Y);
}

Compilation message (stderr)

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

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