Submission #1068176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068176		UmairAhmadMirza	Mechanical Doll (IOI18_doll)	C++17	6 / 100	49 ms	14788 KiB

doll

#include <bits/stdc++.h>
using namespace std;
void answer(vector<int> C, vector<int> X, vector<int> Y);

int const MAXN=2e5+5;
vector<int> nxt[MAXN];

void create_circuit(int m, vector<int> A){
	int n=A.size();
	vector<int> C(m+1);
	vector<int> X,Y;
	C[0]=A[0];
	for(int i=1;i<n;i++)
		nxt[A[i-1]].push_back(A[i]);
	nxt[A[n-1]].push_back(0);
	int s=0;
	for(int i=1;i<=m;i++){
		int sz=nxt[i].size();
		if(sz==0)
			C[i]=0;
		else if(sz==1)
			C[i]=nxt[i][0];
		else if(sz==2){
			s++;
			C[i]=-s;
			X.push_back(nxt[i][0]);
			Y.push_back(nxt[i][1]);
		}
		else if(sz==3){
			s++;
			C[i]=-s;
			X.push_back(-(s+1));
			Y.push_back(-(s+2));
			X.push_back(nxt[i][0]);
			Y.push_back(-s);
			X.push_back(nxt[i][1]);
			X.push_back(nxt[i][2]);
			s+=2;
		}
		else{
			s++;
			C[i]=-s;
			X.push_back(-(s+1));
			Y.push_back(-(s+2));
			X.push_back(nxt[i][0]);
			Y.push_back(nxt[i][2]);
			X.push_back(nxt[i][1]);
			X.push_back(nxt[i][3]);
			s+=2;
		}
	}
	answer(C,X,Y);
}

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