Submission #1041479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041479		amunduzbaev	자동 인형 (IOI18_doll)	C++17	0 / 100	1 ms	348 KiB

doll

#include "doll.h"

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;

template<class T> bool umin(T& a, const T b){ if(a > b) { a = b; return true; } return false; }
template<class T> bool umax(T& a, const T b){ if(a < b) { a = b; return true; } return false; }

void create_circuit(int m, vector<int> a) {
	int n = a.size();
	
	vector<int> c(m + 1), x_(2 * m), y_(2 * m);
	vector<vector<int>> in(m + 1);
	vector<vector<int>> out(m + 1);
	
	a.insert(a.begin(), 0);
	a.push_back(0);
	
	for(int i=0;i <= n;i++){
		out[a[i]].push_back(a[i + 1]);
		in[a[i + 1]].push_back(a[i]);
	}
	
	vector<int> cnt(m + 1), cur(m + 1);
	for(int i=1;i<=m;i++){
		int sz = in[i].size();
		assert((int)out[i].size() == sz);
		cnt[i] = sz;
	}
	
	cnt[0] = 1;
	
	for(int i=1;i<=n+1;i++){
		int x = a[i - 1], y = a[i];
		
		if(cnt[x] == 1 && cnt[y] == 1){
			c[x] = y;
		} 
		
		else if(cnt[x] == 1 && cnt[y] == 2){
			c[x] = -y;
		} 
		
		else if(cnt[x] == 2 && cnt[y] == 1){
			c[x] = -(x + m);
			if(cur[x] == 0){
				x_[x + m - 1] = y;
			} else {
				y_[x + m - 1] = y;
			}
		} 
		
		else if(cnt[x] == 2 && cnt[y] == 2){
			c[x] = -(x + m);
			if(cur[x] == 0){
				x_[x + m - 1] = -y;
			} else {
				y_[x + m - 1] = -y;
			}
		}
		
		cur[x]++;
	}
	
	for(int i=0;i < m;i++){
		x_[i] = i + 1;
		y_[i] = i + 1;
	}
	
	//~ for(int i=0;i<=m;i++){
		//~ cout<<c[i]<<" ";
	//~ }
	
	answer(c, x_, y_);
}

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