Submission #1251557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251557		Zicrus	Migrations (IOI25_migrations)	C++20	0 / 100	27 ms	576 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