Submission #249343

#	Time	Username	Problem	Language	Result	Execution time	Memory
249343		ernestvw	Mechanical Doll (IOI18_doll)	C++11	6 / 100	115 ms	11840 KiB

doll

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

void answer(vector<int> C, vector<int> X, vector<int> Y);

int n, m;
vector<int> a;
vector<vector<int>> adj;

int p = 0;
vector<int> c, x, y;

int new_switch(int g, int d) {
	p++;
	x.push_back(g);
	y.push_back(d);
	return -p;
}

int new_switch(int g) {
	p++;
	x.push_back(-p);
	y.push_back(g);
	return -p;
}

int create(int t, int i, int j) {
	if(i > j) return 0;
	if(i == j) return adj[t][i];
	if(i + 2 == j)
		return new_switch(new_switch(adj[t][i], adj[t][i + 2]), adj[t][i + 1]);
	if(i + 3 == j)
		return new_switch(new_switch(adj[t][i], adj[t][i + 2]), new_switch(adj[t][i + 1], adj[t][i + 3]));
	return new_switch(create(t, i, (i + j) / 2), create(t, (i + j) / 2 + 1, j));
}

void create_circuit(int M, vector<int> A) {
	n = (int)A.size();
	m = M;
	a = A;

	c.assign(m + 1, 0);

	adj.assign(m + 1, vector<int>());
	for(int i = 0; i < n - 1; ++i)
		adj[a[i]].push_back(a[i + 1]);
	adj[0].push_back(a[0]);
	adj[a.back()].push_back(0);
/*
	for(int i = 0; i <= m; ++i) {
		cout << i << ": ";
		for(int j : adj[i])cout<<j<<" ";
		cout<<endl;
	}
*/
	for(int i = 0; i <= m; ++i)
		c[i] = create(i, 0, (int)adj[i].size() - 1);
	
	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