Submission #775257

#	Time	Username	Problem	Language	Result	Execution time	Memory
775257		Baytoro	Mechanical Doll (IOI18_doll)	C++17	53 / 100	91 ms	20780 KiB

doll

#include "doll.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+5;
vector<int> g[NN];
vector<int> x,y;
#define pb push_back
int generate(vector<int> &v, int &s, vector<int> &x, vector<int> &y){
	int sz=v.size();
	int k=1,K=0;
	while(k<sz) k*=2,K++;
	vector<int> rev(k);
	for(int i=0;i<k;i++)
		rev[i]=rev[i/2]/2 | ((i&1) << (K-1));
	const int id=--s;
	for(int i=0;i<(k-1)/2;i++){
		x.pb(--s);
		y.pb(--s);
	}
	for(int i=0;i<k;i++){
		vector<int>& u=i%2? y:x;
		if(rev[i]<k-sz)
			u.pb(id);
		else
			u.pb(v[rev[i]-(k-sz)]);
	}
	return id;
}
void create_circuit(int m, vector<int> a) {
	int n=a.size();
	vector<int> c(m+1);
	c[0]=a[0];
	for(int i=0;i<n-1;i++){
		g[a[i]].push_back(a[i+1]);
		c[a[i]]=a[i+1];
	}
	g[a[n-1]].pb(0);
	int id=0;
	for(int i=1;i<=m;i++){
		int sz=g[i].size();
		if(sz<=1) continue;
		c[i]=generate(g[i],id,x,y);
	}
	answer(c,x,y);
}

• 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