Submission #159713

#	Time	Username	Problem	Language	Result	Execution time	Memory
159713		qkxwsm	Mechanical Doll (IOI18_doll)	C++14	2 / 100	94 ms	17228 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[MAXN];
vi ans, ch[2];
int arr[2 * MAXN];
int good[2 * MAXN];
vi compress;

//proparrgarrte shit up the tree.

void build(int w, int L, int R)
{
	arr[w] = -INF - 1;
	if (L == R)
	{
		//lol reverse the strings.
		if (good[L] != -1)
		{
			arr[w] = good[L];
			// cerr << "GOOD " << w << endl;
		}
		return;
	}
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	build(w << 1 | 1, mid + 1, R);
}
void dfs(int w, int L, int R)
{
	if (L == R) return;
	int mid = (L + R) >> 1;
	dfs(w << 1, L, mid);
	dfs(w << 1 | 1, mid + 1, R);
	// if (arr[w << 1] == -INF - 1)
	// {
	// 	cerr << "FUCK " << w << endl;
	// }
	// assert(arr[w << 1] != -998244354);
	if (arr[w << 1 | 1] == -INF - 1)
	{
		arr[w] = arr[w << 1];
		arr[w << 1] = -INF - 1;
	}
	else
	{
		arr[w] = -INF;
	}
}
void dfs1(int w, int L, int R)
{
	if (arr[w] != -INF) return;
	T++;
	arr[w] = -T;
	ch[0].PB(0); ch[1].PB(0);
	int mid = (L + R) >> 1;
	dfs1(w << 1, L, mid);
	dfs1(w << 1 | 1, mid + 1, R);
	int v = arr[w << 1];
	// cerr << "MODIFY " << -arr[w] - 1 << "ch0 ord " << v;
	ch[0][-arr[w] - 1] = (v >= 0 ? ord[v] : v);
	v = arr[w << 1 | 1];
	// cerr << " ch1 ord " << v << endl;
	ch[1][-arr[w] - 1] = (v >= 0 ? ord[v] : v);
}


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);
	FOR(i, 0, N)
	{
		if (seq[i].empty()) continue;
		if (SZ(seq[i]) == 1)
		{
			ans[i] = seq[i][0];
		}
		else
		{
			ans[i] = -1;
		}
	}
	// cerr << SZ(ans) << endl;
	FOR(i, 1, SZ(A))
	{
		if (SZ(seq[A[i - 1]]) == 1) continue;
		ord.PB(A[i]);
	}
	// for (int x : ord)
	// {
	// 	cerr << x << ' ';
	// }
	// cerr << endl;
	if (SZ(ord) != 0)
	{
		int sz = (32 - __builtin_clz(SZ(ord) - 1));
		FOR(i, 0, (1 << sz)) good[i] = -1;
		FOR(i, 0, SZ(ord))
		{
			int sum = 0;
			FOR(j, 0, sz)
			{
				if (i & (1 << j))
				{
					sum += (1 << (sz - 1 - j));
				}
			}
			good[sum] = i;
			//reverse the
		}
		sz = (1 << sz);
		build(1, 0, sz - 1);
		dfs(1, 0, sz - 1);
		dfs1(1, 0, sz - 1);
	}
	// 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: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56