Submission #732621

#	Time	Username	Problem	Language	Result	Execution time	Memory
732621		SanguineChameleon	Koala Game (APIO17_koala)	C++17	59 / 100	79 ms	340 KiB

koala

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

const int maxn = 1e2 + 20;
int B[maxn];
int R[maxn];
int tr[maxn * 4];

int minValue(int N, int W) {
	// TODO: Implement Subtask 1 solution here.
	// You may leave this function unmodified if you are not attempting this
	// subtask.
	B[0] = 1;
	for (int i = 1; i < N; i++) {
		B[i] = 0;
	}
	playRound(B, R);
	for (int i = 0; i < N; i++) {
		if (R[i] <= B[i]) {
			return i;
		}
	}
	return -1;
}

int maxValue(int N, int W) {
	// TODO: Implement Subtask 2 solution here.
	// You may leave this function unmodified if you are not attempting this
	// subtask.
	int cnt = N;
	for (int i = 0; i < N; i++) {
		B[i] = 1;
	}
	while (cnt > 1) {
		for (int i = 0; i < N; i++) {
			if (B[i] == 1) {
				B[i] = W / cnt;
			}
		}
		playRound(B, R);
		cnt = 0;
		for (int i = 0; i < N; i++) {
			B[i] = (B[i] > 0 && R[i] > B[i]);
			cnt += B[i];
		}
	}
	for (int i = 0; i < N; i++) {
		if (B[i] == 1) {
			return i;
		}
	}
	return -1;
}

int greaterValue(int N, int W, int x, int y) {
	// TODO: Implement Subtask 3 solution here.
	// You may leave this function unmodified if you are not attempting this
	// subtask.
	vector<int> vals = {2, 4, 8};
	for (auto v: vals) {
		for (int i = 0; i < N; i++) {
			B[i] = 0;
		}
		B[x] = v;
		B[y] = v;
		playRound(B, R);
		if ((R[x] > B[x]) != (R[y] > B[y])) {
			if (R[x] > B[x]) {
				return x;
			}
			else {
				return y;
			}
		}
		else {
			if (v == 2 && R[x] <= B[x]) {
				return minValue(N, W) ^ (x ^ y);
			}
		}
	}
	return -1;
}

int greaterValue(int N, int W) {
	return greaterValue(N, W, 0, 1);
}

int merge(int N, int W, int x, int y) {
	if (x == -1) {
		return y;
	}
	else if (y == -1) {
		return x;
	}
	else {
		return greaterValue(N, W, x, y);
	}
}

int order[maxn];
int pos[maxn];

void build(int N, int W, int id, int lt, int rt) {
	if (lt == rt) {
		tr[id] = order[lt];
		pos[order[lt]] = lt;
		return;
	}
	int mt = (lt + rt) / 2;
	build(N, W, id * 2, lt, mt);
	build(N, W, id * 2 + 1, mt + 1, rt);
	tr[id] = merge(N, W, tr[id * 2], tr[id * 2 + 1]);
}

void update(int N, int W, int id, int lt, int rt, int pos) {
	if (lt == rt) {
		tr[id] = -1;
		return;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		update(N, W, id * 2, lt, mt, pos);
	}
	else {
		update(N, W, id * 2 + 1, mt + 1, rt, pos);
	}
	tr[id] = merge(N, W, tr[id * 2], tr[id * 2 + 1]);
}

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

void allValues(int N, int W, int *P) {
	if (W == 2*N) {
		// TODO: Implement Subtask 4 solution here.
		// You may leave this block unmodified if you are not attempting this
		// subtask.
	} else {
		// TODO: Implement Subtask 5 solution here.
		// You may leave this block unmodified if you are not attempting this
		// subtask.
		for (int i = 1; i <= N; i++) {
			order[i] = i - 1;
		}
		shuffle(order + 1, order + N + 1, gen);
		build(N, W, 1, 1, N);
		for (int i = N; i >= 1; i--) {
			P[tr[1]] = i;
			if (i == 1) {
				break;
			}
			update(N, W, 1, 1, N, pos[tr[1]]);
		}
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 22 / 53