oj.uz

Submission #772624

# Submission time Handle Problem Language Result Execution time Memory
772624 2023-07-04T09:08:48 Z SanguineChameleon Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 10 ms 916 KB 
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e4 + 20;
const int lim = 100;
vector<int> type[maxn];
int n, res, pt;

void alternate(int k) {
	k = min(min(k, n - pt), max((int)type[0].size(), (int)type[1].size()));
	if (k == 0) {
		return;
	}
	int t = (int)type[0].size() >= k ? 0 : 1;
	vector<int> q;
	for (int i = 0; i < k; i++) {
		q.push_back(type[t][i]);
		q.push_back(pt + i);
	}
	int cnt = use_machine(q);
	if (t == 0) {
		res += k - (cnt + 1) / 2;
	}
	else {
		res += (cnt + 1) / 2;
	}
	type[t ^ (cnt & 1)].push_back(pt + k - 1);
	if ((cnt >> 1) == (k - 1)) {
		for (int i = 0; i < k - 1; i++) {
			type[t ^ 1].push_back(pt + i);
		}
	}
	else if ((cnt >> 1) == 0) {
		for (int i = 0; i < k - 1; i++) {
			type[t].push_back(pt + i);
		}
	}
	else if (k == 3 && pt + 5 <= n) {
		if ((int)type[t ^ 1].size() < 2) {
			alternate(2);
			res -= 1;
			pt -= 2;
		}
		else {
			cnt = use_machine({type[t ^ 1][0], pt, type[t ^ 1][1], type[t][0], pt + 1, type[t][1], pt + 3, type[t][2], pt + 4}) - 1;
			res += (t ^ (cnt & 1) ^ 1);
			res += (t ^ ((cnt >> 1) & 1) ^ 1); 
			type[t ^ (cnt & 1)].push_back(pt + 4);
			type[t ^ ((cnt >> 1) & 1)].push_back(pt + 3);
			type[t ^ 1 ^ ((cnt >> 2) & 1)].push_back(pt);
			type[t ^ ((cnt >> 2) & 1)].push_back(pt + 1);
			pt += 2;
		}
	}
	pt += k;
}

int count_mushrooms(int _n) {
	n = _n;
	type[0].push_back(0);
	res = 1;
	pt = 1;
	alternate(1);
	alternate(1);
	alternate(2);
	while (pt < n && (int)type[0].size() < lim && (int)type[1].size() < lim) {
		alternate(3);
	}
	while (pt < n) {
		alternate(n);
	}
	return res;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 4 ms 916 KB Output is correct
8 Correct 4 ms 848 KB Output is correct
9 Correct 5 ms 720 KB Output is correct
10 Correct 6 ms 720 KB Output is correct
11 Correct 5 ms 776 KB Output is correct
12 Correct 5 ms 720 KB Output is correct
13 Correct 5 ms 720 KB Output is correct
14 Correct 4 ms 720 KB Output is correct
15 Correct 5 ms 772 KB Output is correct
16 Correct 5 ms 792 KB Output is correct
17 Correct 3 ms 720 KB Output is correct
18 Correct 5 ms 772 KB Output is correct
19 Correct 5 ms 720 KB Output is correct
20 Correct 5 ms 720 KB Output is correct
21 Correct 5 ms 788 KB Output is correct
22 Correct 5 ms 792 KB Output is correct
23 Correct 4 ms 720 KB Output is correct
24 Correct 4 ms 780 KB Output is correct
25 Correct 6 ms 720 KB Output is correct
26 Correct 5 ms 720 KB Output is correct
27 Correct 5 ms 720 KB Output is correct
28 Correct 6 ms 720 KB Output is correct
29 Correct 5 ms 720 KB Output is correct
30 Correct 7 ms 776 KB Output is correct
31 Correct 5 ms 788 KB Output is correct
32 Correct 5 ms 720 KB Output is correct
33 Correct 7 ms 788 KB Output is correct
34 Correct 5 ms 780 KB Output is correct
35 Correct 5 ms 720 KB Output is correct
36 Correct 6 ms 720 KB Output is correct
37 Correct 5 ms 720 KB Output is correct
38 Correct 5 ms 792 KB Output is correct
39 Correct 7 ms 720 KB Output is correct
40 Correct 7 ms 784 KB Output is correct
41 Correct 5 ms 720 KB Output is correct
42 Correct 6 ms 784 KB Output is correct
43 Correct 5 ms 788 KB Output is correct
44 Correct 5 ms 784 KB Output is correct
45 Correct 10 ms 784 KB Output is correct
46 Correct 7 ms 776 KB Output is correct
47 Correct 6 ms 788 KB Output is correct
48 Correct 5 ms 720 KB Output is correct
49 Correct 6 ms 780 KB Output is correct
50 Correct 7 ms 720 KB Output is correct
51 Correct 6 ms 720 KB Output is correct
52 Correct 5 ms 720 KB Output is correct
53 Correct 6 ms 720 KB Output is correct
54 Correct 5 ms 792 KB Output is correct
55 Correct 6 ms 776 KB Output is correct
56 Correct 7 ms 720 KB Output is correct
57 Correct 9 ms 792 KB Output is correct
58 Correct 5 ms 720 KB Output is correct
59 Correct 4 ms 772 KB Output is correct
60 Correct 5 ms 720 KB Output is correct
61 Correct 6 ms 720 KB Output is correct
62 Correct 1 ms 720 KB Output is correct
63 Correct 0 ms 720 KB Output is correct
64 Correct 1 ms 720 KB Output is correct
65 Correct 1 ms 772 KB Output is correct
66 Correct 1 ms 720 KB Output is correct
67 Correct 1 ms 720 KB Output is correct
68 Correct 1 ms 720 KB Output is correct
69 Correct 1 ms 720 KB Output is correct
70 Correct 0 ms 720 KB Output is correct
71 Correct 1 ms 720 KB Output is correct
72 Correct 1 ms 720 KB Output is correct
73 Correct 1 ms 720 KB Output is correct
74 Correct 1 ms 720 KB Output is correct
75 Correct 1 ms 720 KB Output is correct
76 Correct 1 ms 720 KB Output is correct
77 Correct 1 ms 720 KB Output is correct
78 Correct 1 ms 720 KB Output is correct
79 Correct 1 ms 720 KB Output is correct
80 Correct 1 ms 720 KB Output is correct
81 Correct 1 ms 720 KB Output is correct
82 Correct 1 ms 720 KB Output is correct
83 Correct 1 ms 720 KB Output is correct
84 Correct 1 ms 720 KB Output is correct
85 Correct 0 ms 720 KB Output is correct
86 Correct 1 ms 720 KB Output is correct
87 Correct 1 ms 720 KB Output is correct
88 Correct 1 ms 720 KB Output is correct
89 Correct 1 ms 720 KB Output is correct
90 Correct 1 ms 720 KB Output is correct
91 Correct 1 ms 720 KB Output is correct