Submission #238348

#	Time	Username	Problem	Language	Result	Execution time	Memory
238348		Jatana	Mechanical Doll (IOI18_doll)	C++17	12 / 100	1095 ms	8928 KiB

doll

#include "doll.h"
#include <iostream>
#include <algorithm>
#include <cassert>
#include <random>
#include <map>

#define le(v) ((int)v.size())
#define pb push_back
using namespace std;
 
vector<int> X, Y;
 
int inc = 0;
int go(int outs) {
	int id = le(X);
	X.pb(-1e9); Y.pb(-1e9);
	if (outs > 2) {
		if (outs & 1) {
			outs++;
			inc++;
		}
		X[id] = go(outs / 2);
		Y[id] = go(outs / 2);	
	} else assert(outs == 2);
	return -(id + 1);
}
vector<int> gen(int k) {
	if (k == 0) return {0};
	vector<int> sub = gen(k - 1);
	vector<int> real;
	for (int i = 0; i < le(sub); i++) {
		real.pb(sub[i]);
		real.pb(sub[i] + (1 << (k - 1)));
	}
	return real;
}
vector<int> inv(vector<int> p) {
	vector<int> q(le(p));
	for (int i = 0; i < le(p); i++) {
		q[p[i]] = i;
	}
	return q;
}
 
mt19937 rng(1337);
void create_circuit(int M, vector<int> A) {
	X.clear(); Y.clear();
	int N = A.size();
	int cur = A[0];
	A.insert(A.begin(), 0);
	map<int, int> cnt;
	for (int i = 0; i < le(A); i++) {
		cnt[A[i]]++;
	}
	vector<int> C(M + 1, -1e9);
	vector<int> B;
	int sz = 0;
	for (int i = 0; i < le(A); i++) {
		if (cnt[A[i]] == 1) {
			C[A[i]] = (i + 1 < le(A)) ? A[i + 1] : 0;	
		} else {
			sz++;
			B.pb((i + 1 < le(A)) ? A[i + 1] : 0);
		}
	}
	inc = 0;
	int root = go(max(sz, 2));
	if (B.empty()) {
		for (int i = 0; i < le(C); i++) {
			if (C[i] == -1e9) C[i] = 0;
		}
		for (int x : C) {
			cerr << x << " ";
		}
		cerr << endl;
		answer(C, {}, {});
		return;
	}
	for (int i = 0; i < le(C); i++) {
		if (C[i] == -1e9) C[i] = root;
	}
	int wait = inc;
	A = B;
	reverse(A.begin(), A.end());
	while (cur) {
		cerr << cur << " ";
		if (cur > 0) {
			cur = C[cur];
		}	else {
			cur = (-cur) - 1;
			if (X[cur] == -1e9) {
				bool cond = (wait + le(A)) % 2;
				// bool cond = true;
				// bool cond = binary_search(order[real].begin(), order[real].end(), it[real]);
				if (wait
						&& ((le(A) == 1) || cond)) {
					wait--;
					X[cur] = root;
				} else {
					// cout << "decide" << endl;
					X[cur] = A.back();
					A.pop_back();
				}
			}
			swap(X[cur], Y[cur]);
			cur = Y[cur];
		}
	}
	cerr << endl;
	for (int x : C) {
		cerr << x << " ";
	}
	cerr << endl;
	for (int i = 0; i < le(X); i++) {
		cerr << X[i] << " " << Y[i] << endl;
	}
	answer(C, X, Y);
	return;
	vector<bool> del(le(X), false);
	for (int it = 0; it < 100; it++) {
		for (int i = 0; i < le(X); i++) {
			if (del[i]) continue;
			if (X[i] < 0) {
				int j = (-X[i]) - 1;
				if (X[j] == Y[j]) {
					X[i] = X[j];
					del[j] = true;
				}
			}
			if (Y[i] < 0) {
				int j = (-Y[i]) - 1;
				if (X[j] == Y[j]) {
					Y[i] = X[j];
					del[j] = true;
				}
			}
		}
		for (int i = 0; i < le(C); i++) {
			if (C[i] < 0) {
				int j = (-C[i]) - 1;
				if (X[j] == Y[j]) {
					C[i] = X[j];
					del[j] = true;
				}
			}
		}
		if (it == 0) {
			int killed = 0;
			for (int x : del) killed++;
			// cout << "killed: " << killed << endl;
		}
	}
	vector<int> alive;
	for (int i = 0; i < le(X); i++) {
		if (!del[i]) {
			alive.pb(i);
		}
	}
	for (int i = 0; i < le(X); i++) {
		if (X[i] < 0) {
			int id = lower_bound(alive.begin(), alive.end(), (-X[i]) - 1) - alive.begin();
			X[i] = -(id + 1);
		}
		if (Y[i] < 0) {
			int id = lower_bound(alive.begin(), alive.end(), (-Y[i]) - 1) - alive.begin();
			Y[i] = -(id + 1);
		}
	}
	for (int i = 0; i < le(C); i++) {
		if (C[i] < 0) {
			int id = lower_bound(alive.begin(), alive.end(), (-C[i]) - 1) - alive.begin();
			C[i] = -(id + 1);
		}
	}
	int jump = 0;
	for (int i = 0; i < le(X); i++) {
		if (del[i]) {
			jump++;
		} else {
			X[i - jump] = X[i];
			Y[i - jump] = Y[i];
		}
	}
	X.resize(le(X) - jump);
	Y.resize(le(Y) - jump);
	// for (int x : del) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	// for (int i = 0; i < le(X); i++) {
	// 	cout << X[i] << " " << Y[i] << endl;
	// }
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:150:13: warning: unused variable 'x' [-Wunused-variable]
  150 |    for (int x : del) killed++;
      |             ^
doll.cpp:49:6: warning: unused variable 'N' [-Wunused-variable]
   49 |  int N = A.size();
      |      ^

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