Submission #78782

#	Time	Username	Problem	Language	Result	Execution time	Memory
78782		tincamatei	Mechanical Doll (IOI18_doll)	C++14	100 / 100	120 ms	11844 KiB

doll

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

using namespace std;

int lastid;

vector<int> X, Y;
vector<pair<int, pair<bool, int> > > poz;

int dfs(int depth, int N, int p, bool branch, int papa, int bit = 0) {
	if(depth >= 0) {
		int id = -((int)X.size()) - 1;
		X.push_back(0);
		Y.push_back(0);
		if((1 << depth) > N) {
			X[-id - 1] = -1;
			int r1 = dfs(depth - 1, N, p | (1 << bit), 1, id, bit + 1);
			Y[-id - 1] = r1;
		} else {
			int r1 = dfs(depth - 1, (1 << depth), p, 0, id, bit + 1);
			int r2 = dfs(depth - 1, N ^ (1 << depth), p | (1 << bit), 1, id, bit + 1);
			X[-id - 1] = r1;
			Y[-id - 1] = r2;
		}
		return id;
	} else {
		if((1 << bit) - 1 == p) {
			return 0;
		}
		else if(N == 0) {
			return -1;
		}
		else {
			poz.push_back(make_pair(p, make_pair(branch, papa)));
			return 2;
		}
	}
}

void create_circuit(int M, std::vector<int> A) {
	vector<int> C(M + 1, -1);
	
	int maxlg = 0;
	int N = A.size();
	while((1 << maxlg) <= N)
		++maxlg;
	lastid = -maxlg;

	dfs(maxlg - 1, N, 0, 0, 0);
	
	sort(poz.begin(), poz.end());
	
	for(int i = 0; i < poz.size(); ++i) {
		if(poz[i].second.first)
			Y[-poz[i].second.second - 1] = A[i];
		else
			X[-poz[i].second.second - 1] = A[i];
	}

	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<bool, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < poz.size(); ++i) {
      |                 ~~^~~~~~~~~~~~

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