Submission #415697

#	Time	Username	Problem	Language	Result	Execution time	Memory
415697		LastRonin	자동 인형 (IOI18_doll)	C++14	37 / 100	214 ms	31620 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, gln;
vector<int> g[N];
ll cur = 1;
ll L[N], R[N];
bool leave[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, int l = 1, int r = gln) {
	int m = (l + r) >> 1ll;
	if(sost[v] == 0) {
		sost[v] = 1;
		if(l == m) {
			L[v] = p + 1000002;
			return;
		}
		else {
			spusk(L[v], p, l, m);
		}
	}
	else {
	    sost[v] = 0;
		if(m + 1 == r) {
			R[v] = p + 1000002;
			return;			
		}
		else {
			spusk(R[v], p, m + 1, r);
		}
	}
}

void create_circuit(int m, vector<int> a) {
	n = a.size();
	vector<int> C(m + 1), X, Y;    	
	C[0] = -1;
	for(int i = 1; i <= m; i++)C[i] = -1;
	ll z = __lg(n) + 1;	
	build(0, 1, (1<<z));
	gln = (1<<z);
	ll dl = (1<<z) - (n + 1);
	while(dl--)spusk(0, -1);
	for(int i = 0; i < n; i++) {
		spusk(0, a[i]);		
	}
	spusk(0, 0);
	for(int i = 0; i < cur; i++) {
	    if(L[i] > 1000000) {
	    	X.pb(L[i] - 1000002), Y.pb(R[i] - 1000002);
	    }
	    else {
			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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56