Submission #230644

#	Time	Username	Problem	Language	Result	Execution time	Memory
230644		DrSwad	Mechanical Doll (IOI18_doll)	C++17	6 / 100	97 ms	10800 KiB

doll

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

using namespace std;

const int N = int(4e5) + 10;

int c[N];
int x[N], y[N];
int switches_used;

void handle(int from, int L, int R, vector<int> &a) {
	if (R - L + 1 <= 0) return;
	if (R - L + 1 == 1) {
		c[from] = a[0];
		return;
	}

	int at_switch = ++switches_used;
	if (R - L + 1 == a.size()) c[from] = -at_switch;

	int mid = (L + R) >> 1;

	if (R - L + 1 > 2) {
		vector<int> b(R - L + 1);
		for (int i = L; i <= R; i++) {
			if ((i - L) % 2 == 0) b[(i - L) / 2] = a[i];
			else b[mid + (i - L + 1) / 2 - L] = a[i];
		}
		for (int i = L; i <= R; i++) a[i] = b[i - L];
	}

	if (mid - L + 1 == 1) x[at_switch] = a[L];
	else {
		x[at_switch] = -(switches_used + 1);
		handle(from, L, mid, a);
	}

	if (R - mid == 1) y[at_switch] = a[R];
	else {
		y[at_switch] = -(switches_used + 1);
		handle(from, mid + 1, R, a);
	}
}

void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	c[0] = a[0];
	int n = a.size();

	vector<vector<int>> v(m + 1);
	for (int i = 0; i < n - 1; i++) v[a[i]].push_back(a[i + 1]);

	for (int i = 1; i <= m; i++) handle(i, 0, (int)v[i].size() - 1, v[i]);

	answer(vector<int>(c + 0, c + m + 1), vector<int>(x + 1, x + switches_used + 1), vector<int>(y + 1, y + switches_used + 1));
}

Compilation message (stderr)

doll.cpp: In function 'void handle(int, int, int, std::vector<int>&)':
doll.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  if (R - L + 1 == a.size()) c[from] = -at_switch;
      |      ~~~~~~~~~~^~~~~~~~~~~

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