Submission #297683

#	Time	Username	Problem	Language	Result	Execution time	Memory
297683		Berted	Mechanical Doll (IOI18_doll)	C++14	100 / 100	127 ms	11936 KiB

doll

#include "doll.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <queue>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

vector<int> C, X, Y;
vector<pii> candidate;
int sz1 = 0;

inline void fill(int u, int sz, int num)
{
	if (sz == 2)
	{
		candidate.push_back({num | (sz1 / sz), -(u + 1)});
		candidate.push_back({num, u + 1});
	}
	else
	{
		X.push_back(0); Y.push_back(0);
		X[u] = -X.size();
		fill(X.size() - 1, sz / 2, num);
		X.push_back(0); Y.push_back(0);
		Y[u] = -X.size();
		fill(X.size() - 1, sz / 2, num | (sz1 / sz));
	}
}

inline void rs(int u, int sz, int esz, int num)
{
	if (sz == 2)
	{
		candidate.push_back({num | (sz1 / sz), -u - 1});
		if (esz & 1) {candidate.push_back({num, u + 1});}
		else {X[u] = -1;}
	}
	else
	{
		X.push_back(0); Y.push_back(0);
		Y[u] = -Y.size();
		rs(Y.size() - 1, sz / 2, esz, num | (sz1 / sz));
		if (esz & (sz / 2)) 
		{
			X.push_back(0); Y.push_back(0);
			X[u] = -X.size();
			fill(X.size() - 1, sz / 2, num);
		} 
		else {X[u] = -1;}
	}
}

void buildSwitch(int size)
{
	if (size == 2) 
	{
		sz1 = 2;
		fill(0, 2, 0);
		return;
	}
	sz1 = 1;
	while (sz1 < size) {sz1 <<= 1;}

	X.push_back(0); Y.push_back(0);
	X[0] = -X.size();
	X.push_back(0); Y.push_back(0);
	Y[0] = -X.size();

	rs(-X[0] - 1, sz1 / 2, (sz1 / 2) - 1, 0);
	rs(-Y[0] - 1, sz1 / 2, size - (sz1 / 2) - 1, 1);

	//cerr << "SIZE : " << u << " " << adj[u].size() << "\n";
}

void create_circuit(int M, vector<int> A)
{
	C.assign(M + 1, 0);
	A.push_back(0); X.push_back(0); Y.push_back(0);
	for (int i = 0; i <= M; i++) {C[i] = -X.size();}

	buildSwitch(A.size());
	sort(candidate.begin(), candidate.end());
	assert(candidate.size() == A.size());

	for (int i = 0; i < candidate.size(); i++)
	{
		//cerr << "Candidate : " << candidate[i].fst << " " << candidate[i].snd << "\n";
		if (candidate[i].snd < 0)
		{
			Y[-candidate[i].snd - 1] = A[i];
		}
		else
		{
			X[candidate[i].snd - 1] = A[i];
		}
	}

	candidate.clear();

	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < candidate.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