Submission #415783

#	Time	Username	Problem	Language	Result	Execution time	Memory
415783		LastRonin	Mechanical Doll (IOI18_doll)	C++14	100 / 100	198 ms	16620 KiB

doll

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pill pair<ll, ll>
#define ex exit(0)
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;

const ll N = 8e5 + 100;

ll L[N], R[N];
int g[N], cur = 0, n;
vector<pill> x;
bool was[N];

void rec(ll v, ll l, ll r, ll z) {
	ll m = (l + r) >> 1ll;
	if(l == m) {
		if(z == 1)
			L[v] = 1000001;
		return;
	}	
	if(m - l + 1 > z) {
		L[v] = ++cur, rec(L[v], l, m, z);
		R[v] = ++cur, rec(R[v], m + 1, r, 0);
	}
	else {
		L[v] = 1000001, 
		R[v] = ++cur, rec(R[v], m + 1, r, z - (m - l + 1));
	}
}
void spusk(int v) {
	if(v == 1000001)return;
	if(was[v]) {
		was[v] = 0;
	    return (void)(R[v] == 0 ? x.pb(mp(v, 1)) : spusk(R[v]));
	}
	was[v] = 1;
	return (void)(L[v] == 0 ? x.pb(mp(v, 0)) : spusk(L[v]));	
}

void create_circuit(int m, vector<int> a) {
	n = a.size();
	a.pb(0);
	vector<int> C(m + 1, -1), X, Y;
	C[0] = a[0];    	
	ll z = __lg(n) + 1;
	ll d = (1<<z) - (n + 1);
	rec(0, 1, 1<<z, d);
	ll k = (1<<z);
	while(k--)spusk(0);
	for(int i = 1; i < (int)a.size(); i++)
		if(x[i].s)R[x[i].f] = a[i] + 1000002;
		else L[x[i].f] = a[i] + 1000002;
	for(int i = 0; i <= cur; i++) {
		if(L[i] > 1000000) 
			X.pb(L[i] - 1000002);
		else
			X.pb(-(L[i] + 1));
		if(R[i] > 1000000) 
			Y.pb(R[i] - 1000002);
		else
			Y.pb(-(R[i] + 1));
			
	}
	answer(C,X,Y);
}

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