Submission #129253

#	Time	Username	Problem	Language	Result	Execution time	Memory
129253		Shush	Mechanical Doll (IOI18_doll)	C++17	16 / 100	226 ms	17256 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, s;
int h[MAXM + 1];
vector<int> x, y, a, t, c (MAXM + 1, 0);
set <int> el;
vector<vector<int>> nxt(MAXM + 1);

void xypush(int ps, int xi, int yi){
	x.push_back(xi); y.push_back(yi);
	s++;
}

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

void sw2(int i){
	int xi = nxt[i][0], yi = nxt[i][1];
	xypush(s, xi, yi);
}
void sw3(int i){
	int xi = (s + 2) * -1, yi = (s + 3) * -1;
	xypush(s, xi, yi);
	xi = nxt[i][0], yi = s * -1;
	xypush(s, xi, yi);
	xi = nxt[i][1], yi = nxt[i][2];
	xypush(s, xi, yi);
}

void sw4(int i){
	int xi = (s + 2) * -1, yi = (s + 3) * -1;
	xypush(s, xi, yi);
	xi = nxt[i][0], yi = nxt[i][2];
	xypush(s, xi, yi);
    xi = nxt[i][1], yi = nxt[i][3];
    xypush(s, xi, yi);
}

void swsys(int i){
	int j = h[i];
	if(j == 2) {
		t[i] = (s + 1) * -1;
//		cerr << c[i] << " " << i << "\n";
		sw2(i);
	}
	if(j == 3) {
		t[i] = (s + 1) * -1;
//		cerr << c[i] << "\n";
		sw3(i);
	}
	if(j == 4) {
		t[i] = (s + 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]);
		if(i == n - 1) nxt[a[i]].push_back(0);
	}
	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);
	}
//	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: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56