Submission #514935

#	Time	Username	Problem	Language	Result	Execution time	Memory
514935		AdamGS	Mechanical Doll (IOI18_doll)	C++17	100 / 100	157 ms	17972 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int lt[2*LIM], rt[2*LIM], ile[4*LIM], n, m, N=1;
int kier[2*LIM], nr[2*LIM], odw[2*LIM], akt, li;
int kl[2*LIM], kr[2*LIM];
vector<int>V;
void usun(int v, int k) {
	if(v>=N) {
		if(k==1) lt[v]=-1;
		return;
	}
	if(k<=ile[2*v+1]) {
		lt[v]=-1;
		usun(2*v+1, k);
	} else {
		usun(2*v, k-ile[2*v+1]);
	}
}
void create_circuit(int M, vector<int>A) {
	V=A;
	V.pb(0);
	m=M;
	n=V.size();
	while(2*N<n) N*=2;
	rep(i, 2*N) lt[i]=rt[i]=LIM;
	rep(i, N) ile[N+i]=2;
	for(int i=N-1; i; --i) {
		lt[i]=-2*i;
		rt[i]=-2*i-1;
		ile[i]=ile[2*i]+ile[2*i+1];
	}
	usun(1, n);
	int p=1;
	while(li<n) {
		if(!nr[p]) {
			--akt;
			nr[p]=akt;
		}
		kier[p]^=1;
		if(kier[p]) {
			if(lt[p]==LIM) {
				lt[p]=V[li];
				++li;
			}
			if(lt[p]>=0) p=1;
			else p=-lt[p];
		} else {
			if(rt[p]==LIM) {
				rt[p]=V[li];
				++li;
			}
			if(rt[p]>=0) p=1;
			else p=-rt[p];
		}
	}
	p=1;
	while(p) {
		if(!odw[p]) {
			if(lt[p]>=0) kl[-nr[p]]=lt[p];
			else kl[-nr[p]]=nr[-lt[p]];
			if(rt[p]>=0) kr[-nr[p]]=rt[p];
			else kr[-nr[p]]=nr[-rt[p]];
			odw[p]=1;
		}
		kier[p]^=1;
		if(kier[p]) {
			if(lt[p]>0) p=1;
			else p=-lt[p];
		} else {
			if(rt[p]>0) p=1;
			else p=-rt[p];
		}
	}
	vector<int>C, X, Y;
	rep(i, m+1) C.pb(-1);
	for(int i=-1; i>=akt; --i) {
		X.pb(kl[-i]);
		Y.pb(kr[-i]);
	}
	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