Submission #1035680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035680		0npata	Mechanical Doll (IOI18_doll)	C++17	90 / 100	1018 ms	36240 KiB

doll

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

#define vec vector
#define int long long

#define EMPTY 0
#define dbg(v)                                                                 \
	cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

void create_circuit(int32_t M, std::vector<int32_t> A) {
	//cerr << "HELLO" << '\n';
	int N = A.size();
	map<int, int> X, Y;

	int hb = -1;
	for(int i = 0; i<32; i++) {
		if(N & 1ll << i) hb = i;
	}
	assert(hb != -1);

	std::vector<int32_t> C(M + 1, -hb-1);
	int si = hb+2;

	//dbg(hb);

	auto tree = [&](int sz) {
		for(int i = 1; i<sz/2; i++) {
			X[i+si-1] = -(i*2 + si - 1);
			Y[i+si-1] = -(i*2 + 1 + si -1);
		}
		si += sz-1;
	};

	for(int i = hb+1; i>=1; i--) {
		if((1ll<<(i-1)) & N) {
			if(i > 1) {
				X[i] = -si;
				tree(1ll << (i-1));
			}
		}
		else {
			X[i] = -hb-1;
		}
		Y[i] = -i + 1;
		//cerr << X[i] << ' ';
	}
	//cerr << '\n';

	vec<bool> state(N*3+10, false);

	vec<int32_t> a = A;
	a.push_back(1e9);
	int i = 0;

	int cur = 0;
	int cnt = 0;
	do {
		cnt++;
		//cerr << cur << '\n';
		int nxt;
		if(cur < 0) {
			state[-cur] = !state[-cur];
			if(state[-cur]) {
				if(X.count(-cur) == 0) {
					X[-cur] = a[i++];
				}
				nxt = X[-cur];
			}
			else {
				if(Y.count(-cur) == 0) {
					Y[-cur] = a[i++];
				}
				nxt = Y[-cur];
			}
		}
		else {
			nxt = C[cur];
		}
		//if(cnt > 15) break;
		cur = nxt;
	} while(cur != 0);

	int S = si;
	vec<int32_t> XA(si-1, 1e9);
	vec<int32_t> YA(si-1, 1e9);

	for(auto [i, val] : X) {
		XA[i-1] = val;
	}
	for(auto [i, val] : Y) {
		YA[i-1] = val;
	}


	answer(C, XA, YA);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int32_t, std::vector<int>)':
doll.cpp:85:6: warning: unused variable 'S' [-Wunused-variable]
   85 |  int S = si;
      |      ^

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