Submission #577052

#	Time	Username	Problem	Language	Result	Execution time	Memory
577052		Noam527	Game (APIO22_game)	C++17	0 / 100	0 ms	208 KiB

game

#include <bits/stdc++.h>
#include "game.h"
const int OO = 0;
using namespace std;

int getbits(int cnt) {
	return (1 << cnt) - 1;
}
void printbits(int v, int layers = 10) {
	for (int i = 0; i < layers; i++)
		cout << (v >> i & 1);
	cout << endl;
}

int n, k;
vector<vector<int>> g, grev;
vector<int> s, e;

void initial_colors(int layer, int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	for (int i = mid + 1; i <= r; i++)
		s[i] |= 1 << layer, e[i] |= 1 << layer;
	initial_colors(layer + 1, l, mid);
	initial_colors(layer + 1, mid + 1, r);
}

void init(int nn, int kk) {
	n = nn;
	k = kk;
	g.resize(n);
	grev.resize(n);
	s.resize(n);
	e.resize(n);

	initial_colors(0, 0, k - 1);
	int layers = 1;
	while (getbits(layers) < k) layers++;
	for (int i = k; i < n; i++)
		e[i] = getbits(layers);
	if (OO) {
		cout << "initial colors:\n";
		for (int i = 0; i < n; i++) {
			cout << i << '\n';
			printbits(s[i]);
			printbits(e[i]);
		}
	}
}

void forward_dfs(int layer, int v) {
	if (layer > 0 && (e[v] & (1 << (layer - 1))) == 0) return;
	if (s[v] & (1 << layer)) return;
	if (OO) {
		cout << "forward " << layer << " " << v << '\n';
	}
	s[v] |= 1 << layer;
	for (const auto &w : g[v])
		forward_dfs(layer, w);
}

void backward_dfs(int layer, int v) {
	if (layer > 0 && (s[v] & (1 << (layer - 1))) != 0) return;
	if (~e[v] & (1 << layer)) return;
	if (OO) {
		cout << "backward " << layer << " " << v << '\n';
	}
	e[v] ^= 1 << layer;
	for (const auto &w : grev[v])
		backward_dfs(layer, w);
}

int add(int layer, int l, int r, int u, int v) {
	if (OO) {
		cout << "starting layer " << layer << " " << l << " " << r << '\n';
		printbits(s[u]);
		printbits(e[v]);
	}
	if (l == r) return 0;
	if ((s[u] & (1 << layer)) && (~e[v] & (1 << layer))) return 1; // win

	if (s[u] & (1 << layer))
		forward_dfs(layer, v);
	if (~e[v] & (1 << layer))
		backward_dfs(layer, u);

	int mid = (l + r) / 2;
	if (~s[u] & (1 << layer))
		return add(layer + 1, l, mid, u, v);
	return add(layer + 1, mid + 1, r, u, v);
}

int add_teleporter(int u, int v) {
	g[u].push_back(v);
	grev[v].push_back(u);
	return add(0, 0, k - 1, u, v);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40