Submission #415452

#	Time	Username	Problem	Language	Result	Execution time	Memory
415452		_fractal	Mechanical Doll (IOI18_doll)	C++14	53 / 100	237 ms	27844 KiB

doll

#include "doll.h"
#include <iostream>

using namespace std;

vector<int> X, Y;
vector<int> XX, YY;
vector<int> was;
vector<int> go[300200];
int S;

void rec(int pos, int val) {
	if (was[pos] == 0) {
		if (XX[pos] == 0) {
			X[pos] = val;
			XX[pos] = 1;
			was[pos] ^= 1;
			return;
		}
		else {
			was[pos] ^= 1;
			rec(-X[pos] - 1, val);
		}
	}
	else {
		if (YY[pos] == 0) {
			YY[pos] = 1;
			Y[pos] = val;
			was[pos] ^= 1;
			return;
		}
		else {
			was[pos] ^= 1;
			rec(-Y[pos] - 1, val);
		}
	}
}

void build(int v, int cur, int len) {
	if (cur < len) {
		XX[v] = 1;
		YY[v] = 1;
		S++;
		X[v] = -S;
		was.push_back(0);
		X.push_back(0), Y.push_back(0);
		XX.push_back(0), YY.push_back(0);
		S++;
		Y[v] = -S;
		was.push_back(0);
		X.push_back(0), Y.push_back(0);
		XX.push_back(0), YY.push_back(0);
		build(-X[v] - 1, cur + 1, len);
		build(-Y[v] - 1, cur + 1, len);
	}
	else {
		return;
	}
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	vector<int> C(M + 1);
	if (M == 1 && false) {
		C[0] = +1;
		C[1] = -1;
		--N;
		X.resize(N), Y.resize(N);
		for (int k = 1; k <= N; ++k) {
			if (k == 1)
				X[k - 1] = 1;
			else
				X[k - 1] = 1 - k;
			if (k == N)
				Y[k - 1] = 0;
			else
				Y[k - 1] = -1 - k;
		}
		answer(C, X, Y);
		return;
	}
	X.clear(), Y.clear();
	A.push_back(0);
	C[0] = A[0];
	for (int i = 0; i < N; ++i) {
		go[A[i]].push_back(A[i + 1]);
	}
	for (int i = 1; i <= M; ++i) {
		if (go[i].size() == 0)
			continue;
		if (go[i].size() == 1) {
			C[i] = go[i][0];
		}
		else {
			int n = 1, len = 0;
			while (n < go[i].size()) {
				n <<= 1, len++;
			}
			S++;
			was.push_back(0);
			X.push_back(0), Y.push_back(0);
			XX.push_back(0), YY.push_back(0);
			C[i] = -S;
			build(-C[i] - 1, 1, len);
			for (int j = 0; j < go[i].size() - 1; ++j)
				rec(-C[i] - 1, go[i][j]);
			for (int j = go[i].size() - 1; j < n - 1; ++j)
				rec(-C[i] - 1, C[i]);
			rec(-C[i] - 1, go[i].back());
		}
	}
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:96:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    while (n < go[i].size()) {
      |           ~~^~~~~~~~~~~~~~
doll.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for (int j = 0; j < go[i].size() - 1; ++j)
      |                    ~~^~~~~~~~~~~~~~~~~~

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