Submission #238116

#	Time	Username	Problem	Language	Result	Execution time	Memory
238116		Jatana	Mechanical Doll (IOI18_doll)	C++17	16 / 100	127 ms	11760 KiB

doll

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

#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) {
			inc++;
			int lid = le(X);
			X.pb(-1e9); Y.pb(-1e9);
			X[id] = -(lid + 1);
			int A = (outs + 1) / 2;
			int B = (outs) / 2;
			if (A % 2 == 0) swap(A, B);
			if (A > 1) {
				X[lid] = go(A);
			}
			if (B) {
				Y[id] = go(B);
			}
		} else {
			X[id] = go(outs / 2);
			Y[id] = go(outs / 2);	
		}
	} else assert(outs == 2);
	return -(id + 1);
}

void create_circuit(int M, vector<int> A) {
	X.clear(); Y.clear();
	int N = A.size();
	vector<vector<int>> after(M + 1);
	vector<int> wait(M + 1);
	A.pb(0);
	for (int i = 0; i < le(A) - 1; i++) {
		after[A[i]].pb(A[i + 1]);
	}	
	A.pop_back();
	vector<int> C(M + 1);
	C[0] = A[0];
	for (int i = 1; i <= M; i++) {
		if (!after[i].empty()) {
			if (le(after[i]) == 1) {
				C[i] = after[i][0];
			} else {
				int sz = le(after[i]);
				inc = 0;
				C[i] = go(sz);
				wait[i] = inc;
			}
		}
		reverse(after[i].begin(), after[i].end());
	}
	// for (int x : wait) {
	// 	cout << x << " ";
	// }
	// return;
	int cur = C[0];
	int real = -1;
	while (cur) {
		// cerr << cur << " ";
		if (cur > 0) {
			real = cur;
			cur = C[cur];
		}	else {
			cur = (-cur) - 1;
			if (X[cur] == -1e9) {
				if (wait[real]) {
					wait[real]--;
					X[cur] = C[real];
				} else {
					X[cur] = after[real].back();
					after[real].pop_back();
				}
			}
			swap(X[cur], Y[cur]);
			cur = Y[cur];
		}
	}
	// for (int i = 0; i < le(X); i++) {
	// 	cerr << X[i] << " " << Y[i] << ", ";
	// }
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:41:6: warning: unused variable 'N' [-Wunused-variable]
   41 |  int N = A.size();
      |      ^

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