제출 #333718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333718		nicholask	자동 인형 (IOI18_doll)	C++14	6 / 100	212 ms	14276 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
/*
void answer(vector <int> c,vector <int> x,vector <int> y){
	cout<<"C: ";
	for (auto&i:c) cout<<i<<' ';
	cout<<endl;
	cout<<"X: ";
	for (auto&i:x) cout<<i<<' ';
	cout<<endl;
	cout<<"Y: ";
	for (auto&i:y) cout<<i<<' ';
	cout<<endl;
	return;
}
*/
void create_circuit(int m,vector <int> a){
	int n=a.size();
	vector <int> nxt[m+1];
	a.push_back(0);
	for (int i=0; i<n; i++){
		nxt[a[i]].push_back(a[i+1]);
	}
	bool ok=1;
	for (int i=1; i<=m; i++){
		//for (auto&j:nxt[i]) cout<<j<<' ';
		//cout<<endl;
		if (nxt[i].size()>4){
			ok=0;
			break;
		}
	}
	vector <int> c(m+1,0),x,y;
	int cur=0;
	if (ok){
		c[0]=a[0];
		map <int,int> p;
		for (int i=1; i<=n; i++){
			if (nxt[a[i-1]].size()==1){
				c[a[i-1]]=a[i];
			} else if (nxt[a[i-1]].size()==2){
				if (p.count(a[i-1])) c[a[i-1]]=p[a[i-1]];
				else {
					cur--;
					p[a[i-1]]=cur;
					c[a[i-1]]=cur;
					x.push_back(nxt[a[i-1]][0]);
					y.push_back(nxt[a[i-1]][1]);
				}
			} else if (nxt[a[i-1]].size()==3){
				if (p.count(a[i-1])) c[a[i-1]]=p[a[i-1]];
				else {
					cur--;
					p[a[i-1]]=cur;
					c[a[i-1]]=cur;
					x.push_back(cur-1);
					y.push_back(cur-2);
					cur--;
					x.push_back(nxt[a[i-1]][0]);
					y.push_back(nxt[a[i-1]][1]);
					cur--;
					x.push_back(nxt[a[i-1]][2]);
					y.push_back(cur+2);
				}
			} /*else if (nxt[a[i-1]].size()==4){
				if (p.count(a[i-1])) c[a[i-1]]=p[a[i-1]];
				else {
					cur--;
					p[a[i-1]]=cur;
					c[a[i-1]]=cur;
					x.push_back(cur-1);
					y.push_back(cur-2);
					cur--;
					x.push_back(nxt[a[i-1]][0]);
					y.push_back(nxt[a[i-1]][1]);
					cur--;
					x.push_back(nxt[a[i-1]][2]);
					y.push_back(nxt[a[i-1]][3]);
				}
			}*/
		}
	}
	answer(c,x,y);
	return;
}
/*
int main(){
	int n,m;
	cin>>n>>m;
	vector <int> a;
	for (int i=0; i<n; i++){
		int t;
		cin>>t;
		a.push_back(t);
	}
	create_circuit(m,a);
}
*/

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