Submission #415458

#	Time	Username	Problem	Language	Result	Execution time	Memory
415458		LastRonin	자동 인형 (IOI18_doll)	C++14	53 / 100	250 ms	38568 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 n;
vector<int> g[N];
ll cur = 0;
ll L[N], R[N];
bool sost[N];


void build(int v, int l, int r) {
	if(l == r) 
		return;
	ll m = (l + r) >> 1ll;
	if(l != m)
		L[v] = cur++, build(L[v], l, m);	
	if(m + 1 != r)	
	    R[v] = cur++, build(R[v], m + 1, r);
}

void spusk(int v, int p) {
	if(sost[v] == 0) {
		sost[v] = 1;
		if(L[v] == 0) {
			L[v] = -(p + 1);
			return;
		}
		else {
			spusk(L[v], p);
		}
	}
	else {
	    sost[v] = 0;
		if(R[v] == 0) {
			R[v] = -(p + 1);
			return;			
		}
		else {
			spusk(R[v], p);
		}
	}
}

void create_circuit(int m, vector<int> a) {
	n = a.size();
	vector<int> C(m + 1), X, Y;    	
	C[0] = a[0];
	for(int i = 1; i < n; i++) {
	    g[a[i - 1]].pb(a[i]);
	}
	g[a[n - 1]].pb(0);	
	for(int i = 1; i <= m; i++) {
		if(!g[i].size()) 
			continue;
		if(g[i].size() == 1) {
			C[i] = g[i][0];
			continue;
		}
		ll zzz = __lg(g[i].size() - 1) + 1;
		ll ppp = (1<<zzz) - g[i].size();
		ll rt = cur;
		C[i] = -(cur + 1);
		build(cur++, 1, (1<<zzz));
	    while(ppp--)
			spusk(rt, -rt - 1);
		for(auto u : g[i])
			spusk(rt, u);				
	}
	for(int i = 0; i < cur; i++) {
		X.pb(-(L[i] + 1));
		Y.pb(-(R[i] + 1));
	}
/*	for(auto u : C)
		cout << u << " ";
	cout << '\n';
	for(int i = 0; i < cur; i++)
		cout << X[i] << " " << Y[i] << '\n';*/	
	answer(C, X, Y);
}
 /*
int main() {
	ll k, kk;
	cin >> k >> kk;
	vector<int> p;
	for(int i = 0, a; i < kk; i++)
		cin >> a, p.pb(a);
	create_circuit(k, p);	
}      */

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