Submission #721269

#	Time	Username	Problem	Language	Result	Execution time	Memory
721269		ymm	Koala Game (APIO17_koala)	C++17	19 / 100	44 ms	464 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

int minValue(int N, int W) {
	int a[100] = {}, b[100] = {};
	a[0] = 1;
	playRound(a, b);
	Loop (i,0,N) {
		if (a[i] >= b[i])
			return i;
	}
	return -1;
}

int maxValue(int N, int W) {
	int a[100] = {}, b[100] = {};
	bool take[100] = {};
	fill(take, take+N, true);
	fill(b, b+N, 1);
	for (;;) {
		int cnt = 0;
		Loop (i,0,N) {
			take[i] &= a[i] < b[i];
			cnt += take[i];
		}
		if (cnt == 1)
			break;
		Loop (i,0,N)
			a[i] = take[i]? N/cnt: 0;
		playRound(a, b);
	}
	Loop (i,0,N) {
		if (take[i])
			return i;
	}
	return -1;
}

pii test(int *a, int *b, int x)
{
	a[0] = a[1] = x;
	playRound(a, b);
	return {a[0] < b[0], a[1] < b[1]};
}

int greaterValue(int N, int W) {
	int a[100] = {}, b[100] = {};
	auto [x1, y1] = test(a, b, 7);
	if (x1 != y1)
		return x1 < y1;
	if (x1) {
		auto [x2, y2] = test(a, b, 11);
		assert(x2 != y2);
		return x2 < y2;
	} else {
		auto [x2, y2] = test(a, b, 2);
		if (x2 != y2)
			return x2 < y2;
		assert(x2);
		auto [x3, y3] = test(a, b, 4);
		assert(x3 != y3);
		return x3 < y3;
	}
}

void Do(vector<int> vec, vector<int> &ans, int *&p, int *a, int *b)
{
	if (vec.size() <= 1) {
		for (int v : vec)
			ans.push_back(v);
		return;
	}
	int x = *(p++);
	for (int v : vec)
		a[v] = x;
	playRound(a, b);
	vector<int> v1, v2;
	for (int v : vec) {
		(a[v] < b[v]? v2: v1).push_back(v);
		a[v] = 0;
	}
	Do(v1, ans, p, a, b);
	Do(v2, ans, p, a, b);
}

int all200[] = {2,5,16,26,34,51,35,52,27,35,52,35,53,9,19,27,53,35,53,27,53,36,53,16,28,36,54,36,54,28,36,54,36,54,3,9,19,37,54,55,28,55,37,55,16,28,55,37,55,23,37,55,37,55,55,4,15,29,37,56,37,56,23,37,56,38,56,56,6,16,29,56,38,56,23,38,56,38,56,57,10,24,38,57,57,38,57,57,16,29,57,38,57,24,38,57,39,57,57,};
int all100[] = {1,1,1,1,1,1,1,1,1,2,2,2,2,2,3,2,3,3,3,3,3,3,3,4,3,4,2,3,3,4,4,4,4,4,5,3,5,4,5,3,4,4,5,4,5,4,4,6,4,6,2,3,3,4,5,6,6,5,6,6,4,5,6,5,6,7,4,5,7,5,7,5,7,5,7,3,4,4,6,7,6,7,7,5,6,7,6,8,4,5,6,8,6,8,6,6,8,6,8,};

void allValues(int N, int W, int *P) {
	int a[100] = {}, b[100] = {};
	vector<int> vec(N), ans;
	iota(vec.begin(), vec.end(), 0);
	int *p = (W == 100? all100: all200);
	Do(vec, ans, p, a, b);
	Loop (i,0,N)
		P[i] = ans[i];
}

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