Submission #1251214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251214		model_code	Migrations (IOI25_migrations)	C++20	85 / 100	315 ms	524 KiB

migrations

// solution/author-4-16.cpp
// {
//   "verdict": "partially_correct",
//   "except": {
//     "from_root": "correct",
//     "samples": "correct"
//   }
// }
// END HEADER
// ********************************************************
// ** Solution of Z = 4 with 16 writes
// ********************************************************

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

// variables for ahmed
namespace device {
	int N, B;
	vector<int> p;
	int u, v;
	int phase, flag, cur;

	// initialization
	void init(int N_) {
		N = N_;
		B = int(ceil(log2(N)));
		p = { -1 };
		u = 0; v = 0;
		phase = 1; flag = -1; cur = 0;
	}

	// calculate distance
	int dist(int x, int y) {
		int d = 0;
		while (x != y) {
			if (x > y) {
				x = p[x];
			}
			else {
				y = p[y];
			}
			d += 1;
		}
		return d;
	}

	// function for ahmed
	int ahmed(int t, int parent) {
		// step #1. preparation
		p.push_back(parent);
		int d1 = dist(u, v);
		int d2 = dist(u, t);
		int d3 = dist(v, t);
		int pattern;
		if (d1 >= d2 && d1 >= d3) {
			pattern = 0; // Pattern A
		}
		else if (d1 <= d2 && d2 >= d3) {
			v = t;
			pattern = 1; // Pattern B
		}
		else {
			u = v;
			v = t;
			pattern = 2; // Pattern C
		}

		// step #2. if pre-writing phase, don't write
		if (t < N - (B + 2)) {
			return 0;
		}

		// step #3. phase 1
		if (phase == 1) {
			if (pattern == 1 || pattern == 2) {
				phase = 2;
				flag = pattern - 1;
				return 4;
			}
			int bit1 = ((u >> cur) & 1);
			int bit2 = ((v >> cur) & 1);
			cur += 1;
			if (cur == B) {
				phase = 3;
			}
			return bit1 + bit2 * 2;
		}

		// step #4. phase 2
		if (phase == 2) {
			if (pattern == 2) {
				phase = 3;
				return 4;
			}
			int bit = (cur != B ? ((u >> cur) & 1) : flag);
			cur += 1;
			if (cur == B + 1) {
				phase = 3;
			}
			return pattern * 2 + bit;
		}

		// step #5. phase 3
		return pattern;
	}
}

// dummy function for ahmed
int send_message(int N, int pos, int P) {
	if (pos == 1) {
		device::init(N);
	}
	int res = device::ahmed(pos, P);
	return res;
}

// function for hassan
std::pair<int, int> longest_path(vector<int> Cards) {
	// step #1. preparation
	int N = Cards.size();
	int B = int(ceil(log2(N)));

	// step #2. decoding
	int u = -2, v = -1, ubase = 0, vbase = 0, wbase = 0, phase = 1, cur = 0;
	for (int t = max(N - (B + 2), 1); t < N; t++) {
		if (phase == 1) {
			if (Cards[t] == 4) {
				u = -3;
				v = t;
				phase = 2; // Pattern B or C
			}
			else {
				ubase += (Cards[t] % 2) << cur;
				vbase += (Cards[t] / 2) << cur;
				cur += 1;
				if (cur == B) {
					phase = 3;
				}
			}
		}
		else if (phase == 2) {
			if (Cards[t] == 4) {
				u = v;
				v = t; // Pattern C
				phase = 3;
			}
			else {
				int pattern = Cards[t] / 2;
				int bit = Cards[t] % 2;
				wbase += bit << cur;
				cur += 1;
				if (cur == B + 1) {
					phase = 3;
				}
				if (pattern == 1) {
					v = t; // Pattern B
				}
			}
		}
		else {
			if (Cards[t] == 1) {
				v = t; // Pattern B
			}
			if (Cards[t] == 2) {
				u = v;
				v = t; // Pattern C
			}
		}
	}

	// step #3. restoration
	if (phase != 3) {
		ubase = 0;
		vbase = 0;
	}
	if (((wbase >> B) & 1) == 0) {
		ubase += wbase;
		u = (u == -3 ? -2 : u);
		v = (v == -3 ? -2 : v);
	}
	else {
		vbase += wbase - (1 << B);
		u = (u == -3 ? -1 : u);
		v = (v == -3 ? -1 : v);
	}
	u = (u == -2 ? ubase : (u == -1 ? vbase : u));
	v = (v == -2 ? ubase : (v == -1 ? vbase : v));

	return make_pair(u, v);
}

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