Submission #1095855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095855		owoovo	Mechanical Doll (IOI18_doll)	C++17	16 / 100	66 ms	19248 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define F first 
#define S second 
using namespace std;
int m,n,c[800010],x[800010],y[800010],now;
vector<int> e[200010];
vector<int> a;
void create_circuit(int M, std::vector<int> A) {
	now=0;
	n=A.size();
	m=M;
	a=A;
	a.push_back(0);
	for(int i=0;i<n;i++){
		//cout<<a[i]<<" "<<a[i+1]<<'\n';
		e[a[i]].push_back(a[i+1]);
	}
	c[0]=a[0];
	for(int i=1;i<=m;i++){
		int ne=e[i].size();
		if(ne==0)continue;
		if(ne==1){
			c[i]=e[i][0];
			continue;
		}
		if(ne==2){
			now--;
			c[i]=now;
			x[-now]=e[i][0];
			y[-now]=e[i][1];
			continue;
		}
		if(ne==3){
			now--;
			c[i]=now;
			x[-now]=now-1;
			y[-now]=now-2;
			now--;
			x[-now]=now+1;
			y[-now]=e[i][1];
			now--;
			x[-now]=e[i][0];
			y[-now]=e[i][2];
		}
		if(ne==4){
			now--;
			c[i]=now;
			x[-now]=now-1;
			y[-now]=now-2;
			now--;
			x[-now]=e[i][0];
			y[-now]=e[i][2];
			now--;
			x[-now]=e[i][1];
			y[-now]=e[i][3];
		}
	}
	vector<int> C,X,Y;
	C.resize(M+1);
	X.resize(-now);
	Y.resize(-now);
	for(int i=0;i<=m;i++)C[i]=c[i];
	for(int i=0;i<-now;i++){
		X[i]=x[i+1];
		Y[i]=y[i+1];
	}
	answer(C,X,Y);
	return;
}

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