Submission #235550

#	Time	Username	Problem	Language	Result	Execution time	Memory
235550		pit4h	Mechanical Doll (IOI18_doll)	C++14	100 / 100	157 ms	12216 KiB

doll

#include<bits/stdc++.h>
#define st first
#define nd second
#define pii pair<int, int>
#include "doll.h"
using namespace std;
const int MAXN =4e5+5;
int n, base=1, e[2*MAXN][2], rep[2*MAXN];
bool turn[2*MAXN];
void get_edges(int id, int l, int r) {	
	if(l==r) {
		if((base-l) * 2 >= n) {
			e[id][1]=1;
		}
		if((base-l) * 2 + 1 >= n) {
			e[id][0]=1;
		}
		return;
	}
	int m = (l+r)/2;
	e[id][0] = id*2;
	e[id][1] = id*2+1;
	if((base-r) * 2 >= n) {
		e[id][1]=1;
	}
	if((base-m) * 2 >= n) {
		e[id][0]=1;
	}
	if(e[id][0]==id*2) {
		get_edges(id*2, l, m);
	}
	if(e[id][1]==id*2+1) {
		get_edges(id*2+1, m+1, r);
	}
}
void simulate(int id, int v) {
	int nxt = e[id][turn[id]];
	turn[id] ^= 1;
	if(!nxt) {
		e[id][!turn[id]]=-v;
		return;
	}
	simulate(nxt, v);
}
void create_circuit(int m, vector<int> a) {
	vector<int> c(m+1);
	c[0]=a[0];
	a.push_back(0);
	a.erase(a.begin());
	n = a.size();
	for(int i=1; i<=m; ++i) {
		c[i]=-1;
	}	
	while(base < n) {
		base *= 2;
	}
	get_edges(1, 1, base);
	for(int i: a) {
		simulate(1, i);
	}
	int nr = 0;
	for(int i=1; i<2*base; ++i) {
		if(e[i][0]!=0 || e[i][1]!=0) {
			rep[i]=++nr;
		}
	}
	vector<int> x(nr), y(nr);
	for(int i=1; i<2*base; ++i) {
		if(rep[i]!=0) {
			if(e[i][0]<=0) {
				x[rep[i]-1]=-e[i][0];
			}
			else {
				x[rep[i]-1]=-rep[e[i][0]];
			}
			if(e[i][1]<=0) {
				y[rep[i]-1]=-e[i][1];
			}
			else {
				y[rep[i]-1]=-rep[e[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