Submission #1129757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129757		Luvidi	Mechanical Doll (IOI18_doll)	C++20	53 / 100	81 ms	16020 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

int ls;
vector<int> c,x,y;

int ct(vector<int> &out){
	if(out.size()==0)return 0;
	if(out.size()==1)return out[0];
	int k=0,n=out.size();
	while((1<<k)<n)k++;
	int rev[1<<k];
	rev[0]=0;
	for(int i=1;i<(1<<k);i++)rev[i]=rev[i/2]/2|((i&1)<<k-1);
	int id=--ls;
	for(int i=0;i<(1<<k-1)-1;i++){
		x.push_back(--ls);
		y.push_back(--ls);
	}
	for(int i=0;i<(1<<k);i++){
		vector<int> &v=i%2?y:x;
		if(rev[i]<((1<<k)-n))v.push_back(id);
		else v.push_back(out[rev[i]-((1<<k)-n)]);
	}
	return id;
}

void create_circuit(int m, std::vector<int> a) {
	vector<int> out[m+1];
	int n=a.size();
	out[0].push_back(a[0]);
	a.push_back(0);
	for(int i=0;i<n;i++)out[a[i]].push_back(a[i+1]);
	c.resize(m+1);
	for(int i=0;i<=m;i++){
		c[i]=ct(out[i]);
	}
	answer(c,x,y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56