Submission #526241

#	Time	Username	Problem	Language	Result	Execution time	Memory
526241		ntabc05101	Mechanical Doll (IOI18_doll)	C++14	84 / 100	111 ms	9364 KiB

doll

//why am i so stupid?

#include<bits/stdc++.h>
#include "doll.h"
using namespace std;

const int mxN = 1 << 18;

int n, p = 1, cr = 0;
vector<int> x(mxN), y(mxN);
bool e[mxN];

int bld(int l, int r) {
	if (l >= r) {
		return 0;
	}
	if (r < p - n) {
		return -1;
	}

	int z = ++cr, mid = l + r >> 1;
	x[z - 1] = bld(l, mid);
	y[z - 1] = bld(mid + 1, r);
	return -z;
}

void ptr(int z, int t) {
	auto &a = e[-z - 1] ? y[-z - 1]: x[-z - 1];
	e[-z - 1] ^= 1;
	if (!a) {
		a = t;
	}
	else {
		ptr(a, t);
	}
}

void create_circuit(int m, vector<int> a) {
	n = a.size();
	for (; p < n; p <<= 1);

	bld(0, p - 1);
	for (int i = 1; i < n; i++) {
		ptr(-1, a[i]);
	}
	if (n & 1) {
		ptr(-1, -1);
	}
	ptr(-1, 0);

	vector<int> c(m + 1, -1);
	c[0] = a[0];
	x.resize(cr);
	y.resize(cr);

	answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'int bld(int, int)':
doll.cpp:21:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  int z = ++cr, mid = l + r >> 1;
      |                      ~~^~~

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