oj.uz

Submission #721285

# Submission time Handle Problem Language Result Execution time Memory
721285 2023-04-10T15:41:50 Z ymm Koala Game (APIO17_koala) C++17
100 / 100
 52 ms 348 KB 
#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-1;
	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, 12);
		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[ans[i]] = i+1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 4 ms 324 KB Output is correct
3 Correct 4 ms 208 KB Output is correct
4 Correct 4 ms 320 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 320 KB Output is correct
2 Correct 12 ms 208 KB Output is correct
3 Correct 13 ms 320 KB Output is correct
4 Correct 14 ms 208 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 328 KB Output is correct
2 Correct 52 ms 324 KB Output is correct
3 Correct 43 ms 336 KB Output is correct
4 Correct 48 ms 348 KB Output is correct
5 Correct 45 ms 332 KB Output is correct
6 Correct 43 ms 332 KB Output is correct
7 Correct 44 ms 336 KB Output is correct
8 Correct 47 ms 328 KB Output is correct
9 Correct 50 ms 328 KB Output is correct
10 Correct 42 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 8 ms 208 KB Output is correct
4 Correct 6 ms 316 KB Output is correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct
9 Correct 6 ms 208 KB Output is correct
10 Correct 6 ms 208 KB Output is correct
11 Correct 7 ms 208 KB Output is correct
12 Correct 6 ms 208 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 6 ms 208 KB Output is correct
15 Correct 6 ms 208 KB Output is correct
16 Correct 5 ms 320 KB Output is correct
17 Correct 6 ms 208 KB Output is correct
18 Correct 6 ms 208 KB Output is correct
19 Correct 6 ms 292 KB Output is correct
20 Correct 6 ms 208 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 3 ms 320 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 4 ms 208 KB Output is correct
8 Correct 3 ms 208 KB Output is correct
9 Correct 3 ms 208 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 3 ms 208 KB Output is correct
13 Correct 3 ms 208 KB Output is correct
14 Correct 3 ms 208 KB Output is correct
15 Correct 3 ms 208 KB Output is correct
16 Correct 3 ms 208 KB Output is correct
17 Correct 3 ms 208 KB Output is correct
18 Correct 3 ms 208 KB Output is correct
19 Correct 4 ms 208 KB Output is correct
20 Correct 3 ms 208 KB Output is correct
21 Correct 3 ms 208 KB Output is correct
22 Correct 3 ms 208 KB Output is correct
23 Correct 3 ms 208 KB Output is correct
24 Correct 3 ms 208 KB Output is correct
25 Correct 3 ms 208 KB Output is correct
26 Correct 3 ms 208 KB Output is correct
27 Correct 3 ms 208 KB Output is correct
28 Correct 3 ms 208 KB Output is correct
29 Correct 3 ms 208 KB Output is correct
30 Correct 3 ms 208 KB Output is correct
31 Correct 3 ms 208 KB Output is correct
32 Correct 3 ms 208 KB Output is correct
33 Correct 3 ms 208 KB Output is correct
34 Correct 3 ms 208 KB Output is correct
35 Correct 3 ms 208 KB Output is correct
36 Correct 3 ms 320 KB Output is correct
37 Correct 4 ms 208 KB Output is correct
38 Correct 3 ms 208 KB Output is correct
39 Correct 3 ms 208 KB Output is correct
40 Correct 3 ms 296 KB Output is correct