Submission #1072492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072492		pawned	Mechanical Doll (IOI18_doll)	C++17	2 / 100	35 ms	8668 KiB

doll

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "doll.h"

int calc(int x) {	// depth needed
	int curr = 1;
	int res = 0;
	while (curr < x) {
		curr *= 2;
		res++;
	}
	return res - 1;
}

vi calcOrder(int d) {
	vi order = {0};
	for (int j = 0; j <= d; j++) {
		vi order2;
		for (int x : order) {
			order2.pb(x);
			order2.pb(x + (1 << j));
		}
		order = order2;
	}
	return order;
}

void create_circuit(int M, vi A) {
	int N = A.size();
/*	cout<<"A: ";
	for (int i = 0; i < N; i++) {
		cout<<A[i]<<" ";
	}
	cout<<endl;*/
	vi allr[M + 1];
	allr[0].pb(A[0]);
	for (int i = 0; i < N - 1; i++) {
		allr[A[i]].pb(A[i + 1]);
	}
/*	cout<<"allr: "<<endl;
	for (int i = 0; i < M; i++) {
		cout<<i<<": ";
		for (int x : allr[i])
			cout<<x<<" ";
		cout<<endl;
	}*/
	int curr = -1;	// current id
	vi ans(M + 1, 0);
	vector<ii> rit;	// negative to negative
	// create binary tree
	for (int i = 0; i <= M; i++) {
		int K = allr[i].size();
		if (K == 0) {	// never used
			ans[i] = 0;
			continue;
		}
		if (K == 1) {
			ans[i] = allr[i][0];
			continue;
		}
		ans[i] = curr;	// go to binary tree
		int depth = calc(K);
		vi order = calcOrder(depth);
		// order[i]: time that cell i is used
/*		cout<<"order: ";
		for (int x : order)
			cout<<x<<" ";
		cout<<endl;*/
		vi conv((1 << (depth + 1)), -1);
		// conv[i]: cell used at time i
		for (int j = 0; j < (1 << (depth + 1)); j++) {
			conv[order[j]] = j;
		}
		for (int j = 0; j < (1 << depth) - 1; j++) {
			rit.pb({curr - (2 * j + 1), curr - (2 * j + 2)});
		}
		for (int j = (1 << depth) - 1; j < (1 << (depth + 1)) - 1; j++) {
			int pos = j - ((1 << depth) - 1);
			ii tp = {0, 0};
			if (order[2 * pos] < K)
				tp.fi = allr[i][order[2 * pos]];
			if (order[2 * pos + 1] < K)
				tp.se = allr[i][order[2 * pos + 1]];
			rit.pb(tp);
		}
		curr -= ((1 << (depth + 1)) - 1);
	}
	vi ans1, ans2;
	for (ii p : rit) {
		ans1.pb(p.fi);
		ans2.pb(p.se);
	}
	answer(ans, ans1, ans2);
}

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