Submission #380448

#	Time	Username	Problem	Language	Result	Execution time	Memory
380448		rainboy	Koala Game (APIO17_koala)	C11	100 / 100	91 ms	508 KiB

koala

#include "koala.h"
#include <string.h>
#include <stdio.h>
 
#define N	100
 
int minValue(int n, int w) {
	static int bb[N], rr[N];
	int i;
 
	memset(bb, 0, n * sizeof *bb), bb[0] = 1;
	playRound(bb, rr);
	for (i = 1; i < n; i++)
		if (rr[i] == 0)
			return i;
	return 0;
}
 
int aa[] = { 2, 4, 11 };
 
int maxValue(int n, int w) {
	static int bb[N], rr[N];
	int i, r;
 
	for (i = 0; i < N; i++)
		bb[i] = 1;
	playRound(bb, rr);
	for (r = 0; r < 3; r++) {
		for (i = 0; i < N; i++)
			if (bb[i] && rr[i] > bb[i])
				bb[i] = aa[r];
			else
				bb[i] = 0;
		playRound(bb, rr);
	}
	for (i = 0; i < N; i++)
		if (bb[i] && rr[i] > bb[i])
			return i;
	return -1;
}
 
int greaterValue(int n, int w) {	/* https://usaco.guide/solutions/apio-17-koala?lang=cpp#subtask-3 */
	static int bb[N], rr[N];
	int lower, upper;

	lower = 1, upper = 9;
	while (1) {
		int b = (lower + upper) / 2; 

		memset(bb, 0, N * sizeof *bb), bb[0] = bb[1] = b;
		playRound(bb, rr);
		if (rr[0] > bb[0] && rr[1] > bb[1])
			lower = b + 1;
		else if (rr[0] <= bb[0] && rr[1] <= bb[1])
			upper = b - 1;
		else
			return rr[1] > bb[1];
	}
}
 
int n_;
 
int compare(int i, int j) {
	static int bb[N], rr[N];
 
	memset(bb, 0, n_ * sizeof *bb);
	bb[i] = bb[j] = n_;
	playRound(bb, rr);
	return rr[i] > bb[i] ? 1 : -1;
}
 
void sort(int *ii, int l, int r) {
	static int jj[N];
	int m, i, j, k;
 
	if (r - l == 1)
		return;
	m = (l + r) / 2;
	sort(ii, l, m), sort(ii, m, r);
	i = l, j = m, k = l;
	while (i < m && j < r)
		jj[k++] = compare(ii[i], ii[j]) < 0 ? ii[i++] : ii[j++];
	while (i < m)
		jj[k++] = ii[i++];
	while (j < r)
		jj[k++] = ii[j++];
	memcpy(ii + l, jj + l, (r - l) * sizeof *jj);
}
 
int parts[][3] = {
	{ 0, 100, 1 }, { 0, 50, 1 }, { 0, 50, 2 }, { 50, 100, 1 }, { 50, 100, 2 },
	{ 0, 25, 1 }, { 0, 25, 2 }, { 0, 25, 3 }, { 0, 25, 4 }, { 25, 34, 2 },
	{ 25, 34, 3 }, { 25, 34, 4 }, { 25, 34, 5 }, { 25, 34, 8 }, { 34, 50, 2 },
	{ 34, 50, 3 }, { 34, 50, 4 }, { 34, 50, 5 }, { 34, 50, 6 }, { 50, 60, 2 },
	{ 50, 60, 3 }, { 50, 60, 4 }, { 50, 60, 5 }, { 50, 60, 7 }, { 50, 60, 10 },
	{ 60, 75, 2 }, { 60, 75, 3 }, { 60, 75, 4 }, { 60, 75, 5 }, { 75, 100, 2 },
	{ 75, 100, 3 }, { 75, 100, 4 }, { 0, 13, 1 }, { 0, 13, 2 }, { 0, 13, 3 },
	{ 0, 13, 4 }, { 0, 13, 6 }, { 13, 17, 2 }, { 13, 17, 3 }, { 13, 17, 4 },
	{ 17, 19, 3 }, { 20, 25, 2 }, { 20, 25, 3 }, { 20, 25, 4 }, { 20, 25, 5 },
	{ 25, 28, 3 }, { 25, 28, 5 }, { 28, 30, 4 }, { 34, 40, 3 }, { 34, 40, 4 },
	{ 34, 40, 5 }, { 34, 40, 7 }, { 40, 43, 4 }, { 40, 43, 6 }, { 43, 45, 5 },
	{ 47, 50, 4 }, { 47, 50, 6 }, { 51, 54, 5 }, { 51, 54, 6 }, { 54, 56, 6 },
	{ 60, 63, 5 }, { 60, 63, 7 }, { 63, 67, 4 }, { 63, 67, 5 }, { 63, 67, 7 },
	{ 67, 69, 7 }, { 69, 71, 7 }, { 71, 75, 5 }, { 71, 75, 6 }, { 71, 75, 8 },
	{ 75, 83, 3 }, { 75, 83, 4 }, { 75, 83, 5 }, { 75, 83, 7 }, { 75, 83, 10 },
	{ 83, 88, 4 }, { 83, 88, 5 }, { 83, 88, 6 }, { 83, 88, 9 }, { 88, 91, 6 },
	{ 88, 91, 8 }, { 91, 100, 3 }, { 91, 100, 4 }, { 91, 100, 5 }, { 91, 100, 6 },
	{ 91, 100, 8 }, { 91, 100, 11 }, { 0, 7, 1 }, { 0, 7, 2 }, { 0, 7, 3 },
	{ 7, 9, 2 }, { 34, 36, 5 }, { 76, 78, 7 }, { 78, 80, 7 }, { 92, 95, 6 },
	{ 92, 95, 8 }, { 0, 4, 1 }, { 0, 4, 2 }, { 0, 2, 1 }, 
}; /* done by hand */
 
void allValues(int n, int w, int *pp) {
	static int ii[N];
	int i;
 
	for (i = 0; i < n; i++)
		ii[i] = i;
	if (w == n * 2)	/* mergesort */
		n_ = n, sort(ii, 0, n);
	else {	/* quicksort */
		static int bb[N], rr[N];
		int h;
 
		for (h = 0; h < N - 1; h++) {
			int l = parts[h][0], r = parts[h][1], b = parts[h][2], tmp;
 
			memset(bb, 0, n * sizeof *bb);
			for (i = l; i < r; i++)
				bb[ii[i]] = b;
			playRound(bb, rr);
			while (l < r)
				if (rr[ii[l]] <= bb[ii[l]])
					l++;
				else {
					r--;
					tmp = ii[l], ii[l] = ii[r], ii[r] = tmp;
				}
		}
	}
	for (i = 0; i < n; i++)
		pp[ii[i]] = i + 1;
}

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