Submission #425157

#	Time	Username	Problem	Language	Result	Execution time	Memory
425157		Pbezz	Mechanical Doll (IOI18_doll)	C++14	16 / 100	102 ms	12120 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;

void create_circuit(int M, std::vector<int> A) {
	int n = A.size(),k,S=-1,i;

	vector<vector<int>>adj(M+5);
	std::vector<int> X, Y;
	std::vector<int> C(M + 1);
	C[0]=A[0];
	for(i=0;i<n-1;i++){
	//C[A[i]]=A[i+1];
	adj[A[i]].pb(A[i+1]);
}
	adj[A[n-1]].pb(0);

	for(i=1;i<=M;i++){
	k=adj[i].size();
//	cout<<i<<" #"<<k<<endl;
	if(k==1){
	C[i]=adj[i][0];
	}else if(k==2){

	C[i]=S;
	X.pb(adj[i][0]);
	Y.pb(adj[i][1]);
	S--;

	}else if(k==3){

	C[i]=S;
	X.pb(S-1);
	Y.pb(S-2);
	S--;

	X.pb(adj[i][0]);
	Y.pb(C[i]);
	S--;

	X.pb(adj[i][1]);
	Y.pb(adj[i][2]);
	S--;

	}else if(k==4){
	C[i]=S;
	X.pb(S-1);
	Y.pb(S-2);
	S--;

	X.pb(adj[i][0]);
	Y.pb(adj[i][2]);
	S--;

	X.pb(adj[i][1]);
	Y.pb(adj[i][3]);
	S--;
}


}
/*
	for(i=0;i<=M;i++)cout<<C[i]<<" ";
	cout<<endl;
	cout<<S<<endl;
	for(auto u:X)cout<<u<<" ";
	cout<<endl;
	for(auto u:Y)cout<<u<<" ";
	cout<<endl;
*/

	
  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