Submission #129250

#	Time	Username	Problem	Language	Result	Execution time	Memory
129250		Shush	Mechanical Doll (IOI18_doll)	C++17	2 / 100	98 ms	23132 KiB

doll

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

struct sw{
	int id, x, y;
};

const int MAXM = 1e5;
const int MAXN = 1e6;

bool p = true;
int n, m;
int h[MAXM + 1];
vector<int> x, y, a, t, c (MAXM + 1, 0);
set <int> el;
vector<vector<int>> nxt(MAXM + 1);
vector<sw> s;

void show(vector<int> t){
	for(int i : t) cerr << i << " ";
	cerr << "\n";
}

void sw2(int i){
	int  id = (s.size() + 1) * -1, xi = nxt[i][0], yi = nxt[i][1];
//	cerr << id << " " << xi << " " << yi << "\n";
	s.push_back((sw){id, xi, yi});
	return;
}
void sw3(int i){
	int  id = (s.size() + 1) * -1;
	int xi = id - 1, yi = nxt[i][1];
	s.push_back((sw){id, xi, yi});
	id = xi, xi = nxt[i][0], yi = nxt[i][2];
	s.push_back((sw){id, xi, yi});
}

void sw4(int i){
	int  id = (s.size() + 1) * -1;
	int xi = id - 1, yi = id - 2, idp = id;
	s.push_back((sw){id, xi, yi});
	id = xi, xi = nxt[i][0], yi = nxt[i][2];
	s.push_back((sw){id, xi, yi});
	id = idp - 2, xi = nxt[i][1], yi = nxt[i][3];
	s.push_back((sw){id, xi, yi});
}

void swsys(int i){
	int j = h[i];
	if(j == 2) {
		c[i] = (s.size() + 1) * -1;
//		cerr << c[i] << " " << i << "\n";
		sw2(i);
	}
	if(j == 3) {
		c[i] = (s.size() + 1) * -1;
//		cerr << c[i] << "\n";
		sw3(i);
	}
	if(j == 4) {
		c[i] = (s.size() + 1) * -1;
//		cerr << c[i] << "\n";
		sw4(i);
	}
}

void create_circuit(int M, std::vector<int> A) {
	m = M, n = A.size(); a = A;
	t = vector<int> (m + 1, 0);
	//Hashing
	for(int i = 0; i < n; i++) {
		h[a[i]]++;
		el.insert(a[i]);
		if(i > 0) nxt[a[i - 1]].push_back(a[i]);
	}
	t[0] = a[0];
	for(int i = 0; i < n - 1; i++){
		if(h[a[i]] == 1) t[a[i]] = a[i + 1];
		else p = false;
	}
	if(p) { //Subtask 1
		answer(t, x, y);
		return;
	}
//	Creating Switch contraptions
	for(int i : el){
		if(h[i] > 1) swsys(i);
	}
	x = y = vector<int>(s.size());
	for(int i = 0; i < (int)s.size(); i++){
		x[i] = s[i].x;
		y[i] = s[i].y;
	}
	for(int i = 0; i < n - 1; i++){
//		cerr << i << " " << c[i] << "\n";
		if(c[i] != 0) t[i] = c[i];
	}
//	show(t);
//	for(int i = 0; i < x.size(); i++){
//		cerr << x[i] << " " << (i + 1) * - 1 << " " << y[i] << "\n";
//	}
	answer(t, x, y);
}

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