Submission #136324

#	Time	Username	Problem	Language	Result	Execution time	Memory
136324		Boxworld	Mechanical Doll (IOI18_doll)	C++14	16 / 100	108 ms	19612 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN=400010;
typedef vector<int> vec;
vec G[maxN];
int tmp=-1;
void create_circuit(int M, std::vector<int> A){
	A.push_back(0);
	int N=A.size();
	vec C(M+1),X,Y;
	C[0]=A[0];
	for (int i=0;i<N-1;i++)G[A[i]].push_back(A[i+1]);
	for (int i=1;i<=M;i++){
		if (G[i].empty())C[i]=0;
		else{
			int x=G[i].size();
			if (x==1)C[i]=G[i][0];
			else if (x==2){
				C[i]=tmp;
				X.push_back(G[i][0]);
				Y.push_back(G[i][1]);
				tmp-=1;
			}else if (x==3){
				C[i]=tmp;
				X.push_back(tmp-1);//-1
				Y.push_back(tmp-2);//-1
				X.push_back(G[i][0]);//-2
				Y.push_back(tmp);//-2
				X.push_back(G[i][1]);//-3
				Y.push_back(G[i][2]);//-3
				tmp-=3;
			}else if (x==4){
				C[i]=tmp;
				X.push_back(tmp-1);//-1
				Y.push_back(tmp-2);//-1
				X.push_back(G[i][0]);//-2
				Y.push_back(G[i][2]);//-2
				X.push_back(G[i][1]);//-3
				Y.push_back(G[i][3]);//-3
				tmp-=3;
			}
		}
	}
//	for (int i=0;i<=M;i++)printf("%d: %d\n",i,C[i]);
//	for (int i=0;i<X.size();i++)printf("%d: [x]%3d [y]%3d\n",-1-i,X[i],Y[i]);
	answer(C,X,Y);
}

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