Submission #159834

#	Time	Username	Problem	Language	Result	Execution time	Memory
159834		qkxwsm	Mechanical Doll (IOI18_doll)	C++14	53 / 100	261 ms	28152 KiB

doll

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 270013
#define INF 998244353

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M, T;
vi ord;
vi seq[2 * MAXN];
vi ans, ch[2];
int rv[2 * MAXN], arr[2 * MAXN];
int dif;

void build(int w, int L, int R)
{
	if (L == R)
	{
		L = rv[L];
		if (L < dif)
		{
			arr[w] = -1;
			return;
		}
		L -= dif;
		arr[w] = ord[L];
		//do smth
		return;
	}
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	build(w << 1 | 1, mid + 1, R);
	arr[w] = -w;
}
void dfs(int w, int L, int R)
{
	if (L == R) return;
	ch[0][w - 1] = arr[w << 1];
	ch[1][w - 1] = arr[w << 1 | 1];
	int mid = (L + R) >> 1;
	dfs(w << 1, L, mid);
	dfs(w << 1 | 1, mid + 1, R);
}


void create_circuit(int n, vi A)
{
	n++; N = n;
	A.insert(A.begin(), 0);
	A.PB(0);
	M = SZ(A);
	FOR(i, 0, M - 1)
	{
		seq[A[i]].PB(A[i + 1]);
	}
	ans.resize(N);
	bool solve = false;
	FOR(i, 0, N)
	{
		if (seq[i].empty()) continue;
		if (SZ(seq[i]) == 1)
		{
			ans[i] = seq[i][0]; continue;
		}
		else if (SZ(seq[i]) == 2)
		{
			T++;
			ans[i] = -T;
			ch[0].PB(seq[i][0]);
			ch[1].PB(seq[i][1]);
			continue;
		}
		else
		{
			solve = true;
		}
	}
	if (solve)
	{
		ch[0].clear(); ch[1].clear();
		FOR(i, 0, N)
		{
			if (SZ(seq[i]) <= 1) continue;
			ans[i] = -1;
		}
		T = 0;
	}
	// ans[0] = A[1];
	// cerr << SZ(ans) << endl;
	FOR(i, 2, M)
	{
		if (SZ(seq[A[i - 1]]) == 1) continue;
		ord.PB(A[i]);
	}
	// for (int x : ord)
	// {
	// 	cerr << x << ' ';
	// }
	// cerr << endl;
	if (solve && SZ(ord) != 0)
	{
		int sz = 1;
		while(sz < SZ(ord)) sz *= 2;
		sz = 31 - __builtin_clz(sz);
		FOR(i, 0, (1 << sz))
		{
			int sum = 0;
			FOR(j, 0, sz)
			{
				if (i & (1 << j))
				{
					sum += (1 << (sz - 1 - j));
				}
			}
			rv[sum] = i;
			//reverse the
		}
		sz = (1 << sz);
		dif = sz - SZ(ord);
		ch[0].resize(sz - 1); ch[1].resize(sz - 1);
		build(1, 0, sz - 1);
		dfs(1, 0, sz - 1);
	}
	// assert(SZ(ch[0]) <= 2 * (SZ(A) - 2));
	// cerr << "SZ " << SZ(ch[0]) << endl;
	answer(ans, ch[0], ch[1]);
	//let's try for 100
	//build a segtree on ord. except we need to apply compression.
}

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