Submission #108024

#	Time	Username	Problem	Language	Result	Execution time	Memory
108024		Noam527	Mechanical Doll (IOI18_doll)	C++17	100 / 100	260 ms	18760 KiB

doll

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

void answer(vector<int> C, vector<int> X, vector<int> Y);

struct node {
	int tar, l, r, ind;
	int mode;
	node() {}
	node(int ii) {
		tar = 1;
		ind = ii;
		l = r = md;
		mode = 0;
	}
	node(int ll, int rr, int ii) {
		l = ll;
		r = rr;
		ind = ii;
		tar = 0;
		mode = 0;
	}
	int next() {
		if (mode) return mode ^= 1, r;
		return mode ^= 1, l;
	}
};

int n, m;
vector<node> g;
vector<int> order;

void walk() {
	int v = (int)g.size() - 1;
	while (order.size() < n) {
		if (g[v].tar) {
			order.push_back(v);
			v = (int)g.size() - 2;
		}
		else
			v = g[v].next();
	}
}

void create_circuit(int M, vector<int> A) {
	A.push_back(n);
	n = A.size(), m = M;
	for (int i = 0; i < n; i++)
		g.push_back(node(i));
	int nxt = 0, lst = n - 1;
	int S = 0;
	while (nxt < lst) {
		while (nxt <= lst) {
			g.push_back(node(nxt, (nxt + 1 <= lst ? nxt + 1 : md), -1));
			S++;
			nxt = min(nxt + 2, lst + 1);
		}
		lst = (int)g.size() - 1;
	}
	g.push_back(node(nxt, nxt, -1));
	for (auto &i : g)
		if (i.r == md) i.r = (int)g.size() - 2;
	for (auto &i : g)
		swap(i.l, i.r);
	
	nxt = 0;
	for (int i = (int)g.size() - 1; g[i].tar == 0; i--)
		g[i].ind = nxt++;
	walk();

	vector<int> C(m + 1, -1);
	vector<int> X(S), Y(S);
	for (int i = 0; i < n; i++)
		g[order[i]].mode = A[i];
	for (int i = n; i + 1 < g.size(); i++) {
		if (g[i].l < n) X[g[i].ind - 1] = g[g[i].l].mode;
		else X[g[i].ind - 1] = -g[g[i].l].ind;

		if (g[i].r < n) Y[g[i].ind - 1] = g[g[i].r].mode;
		else if (g[i].r == md) Y[g[i].ind - 1] = 0;
		else Y[g[i].ind - 1] = -g[g[i].r].ind;
	}
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void walk()':
doll.cpp:43:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |  while (order.size() < n) {
      |         ~~~~~~~~~~~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:83:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = n; i + 1 < g.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