Submission #1251566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251566		Zicrus	Migrations (IOI25_migrations)	C++20	0 / 100	27 ms	412 KiB

migrations

#include <bits/stdc++.h>
#include "migrations.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(34056237);
ll _ = 0;

ll n__;
vector<ll> p__;
vector<ll> depth__;
ll mx_id_1__ = 0, mx_id_2__ = 0;
queue<ll> seq__;
int prev_jam__ = 0;
ll sz__ = 0;

void calc_seq(ll i1, ll i2) {
	seq__ = queue<ll>();
	for (ll mask = 1; mask < n__; mask *= 2) {
		seq__.push((i1 / mask) & 1);
	}
	for (ll mask = 1; mask < n__; mask *= 2) {
		seq__.push((i2 / mask) & 1);
	}
}

int send_message(int N, int i, int pi) {
	if (i == 1) {
		n__ = N;
		p__ = vector<ll>(n__);
		depth__ = vector<ll>(n__);
		calc_seq(0, 0);
		sz__ = seq__.size();
		seq__ = queue<ll>();
	}

	ll rem_inc = n__ - i;
	if (rem_inc == sz__ + 1) {
		calc_seq(mx_id_1__, mx_id_2__);
		seq__.push(0);
	}
	bool sending = (rem_inc <= seq__.size() + 1);

	int jam = 0;
	p__[i] = pi;
	depth__[i] = depth__[pi] + 1;
	if (depth__[i] > depth__[mx_id_1__]) {
		mx_id_1__ = i;
		if (sending) {
			jam = 3;
		}
	}
	if (!sending) return 0;
	
	if (jam) {
		if (prev_jam__) {
			if (jam == prev_jam__) { // minor
				ll nxt = seq__.front(); seq__.pop();
				return nxt + 2;
			}
			else { // major
				return 4;
			}
		}

		if (!prev_jam__) prev_jam__ = jam;
		return jam;
	}

	ll nxt = seq__.front(); seq__.pop();
	return nxt;
}

std::pair<int, int> longest_path(std::vector<int> s) {
	ll n = s.size();
	calc_seq(0, 0);
	sz__ = seq__.size();
	seq__ = queue<ll>();
	mx_id_1__ = mx_id_2__ = prev_jam__ = 0;

	bool jam_1 = false, jam_2 = false;
	ll first = n - (sz__ + 1);
	for (ll i = first; i < n; i++) {
		if (!prev_jam__) {
			if (s[i] >= 3) { // jam
				prev_jam__ = s[i];
				if (s[i] == 3) {
					mx_id_1__ = i;
					jam_1 = true;
				}
				if (s[i] == 4) {
					mx_id_2__ = i;
					jam_2 = true;
				}
				continue;
			}
			seq__.push(s[i]);
		}
		else {
			if (s[i] == 4) { // major jam
				if (prev_jam__ == 3) {
					mx_id_2__ = i;
				}
				if (prev_jam__ == 4) {
					mx_id_1__ = i;
				}
				jam_1 = jam_2 = true;
				continue;
			}
			seq__.push(s[i] & 1);
			ll j = s[i] / 2;
			if (j) { // minor jam
				if (prev_jam__ == 3) {
					mx_id_1__ = i;
				}
				if (prev_jam__ == 4) {
					mx_id_2__ = i;
				}
			}
		}
	}

	if (seq__.size() < sz__) return {mx_id_1__, mx_id_2__};

	ll r_1 = 0, r_2 = 0;
	for (ll mask = 1; mask < n; mask *= 2) {
		r_1 |= mask * seq__.front(); seq__.pop();
	}
	for (ll mask = 1; mask < n; mask *= 2) {
		r_2 |= mask * seq__.front(); seq__.pop();
	}
	if (!jam_1) mx_id_1__ = r_1;
	if (!jam_2) mx_id_2__ = r_2;
	return {mx_id_1__, mx_id_2__};
}

#ifdef TEST
#include "grader.cpp"
#endif

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 70