#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "mushrooms.h"
VVI gp = {
{-1, 1, 2, 6, 12, 20, 28, 34, 38, -1},
{},
{-1, -1, -1, 3, 4, -1, 5, -1, -1, -1},
{},
{},
{},
{-1, 7, -1, 8, 9, 10, 11, -1, -1, -1},
{},
{},
{},
{},
{},
{-1, 13, 14, 15, 16, 17, 18, 19, -1, -1},
{},
{},
{},
{},
{},
{},
{},
{-1, 21, 22, 23, 24, 25, 26, 27, -1, -1},
{},
{},
{},
{},
{},
{},
{},
{-1, -1, -1, 29, 30, 31, 32, 33, -1, -1},
{},
{},
{},
{},
{},
{-1, -1, 35, -1, 36, 37, -1, -1, -1, -1},
{},
{},
{},
{}
};
vector<string> harc = {
"A0B01C1DE",
"00111",
"001ABCD1E",
"10111",
"00110",
"00100",
"00A1BCD1E",
"01111",
"00011",
"10110",
"00101",
"10100",
"1A0B0C0DE",
"00000",
"10011",
"00010",
"10101",
"01100",
"11111",
"01110",
"1A0B0C0DE",
"10000",
"00001",
"10010",
"01011",
"11100",
"01101",
"11110",
"0AB1C10DE",
"11101",
"01000",
"11011",
"01010",
"10001",
"0011ABCDE",
"11000",
"11010",
"01001",
"11001"
};
const int LASTLIM = 141;
int count_mushrooms(int n) {
VI mek, zro;
zro.pb(0);
int cnt0 = 1;
int last = 1;
auto ask = [&](string s, bool partial = false) {
int m = 0;
int z = 0;
VI ret;
int change = 0;
for (char ch : s) {
if (ch == '0') ret.pb(zro[z++]);
else if (ch == '1') ret.pb(mek[m++]);
else ret.pb(last++), change++;
}
last -= change;
return use_machine(ret);
};
auto classify = [&](string s) {
int j = 0;
replr(i, last, last+s.size()-1) {
if (s[j++] == '0') {
zro.pb(i);
cnt0++;
} else {
mek.pb(i);
}
}
last += s.size();
};
auto expand = [&]() {
int u = 0;
while (true) {
int ret = ask(harc[u], true);
u = gp[u][ret];
if (harc[u].size() == 5) {
classify(harc[u]);
break;
}
}
};
if (n >= 20) {
if (!ask("0x")) {
classify("0");
} else {
classify("1");
if (!ask("0x")) classify("0");
else classify("1");
}
rep(_, 1) {
if (last+1 >= n) break;
if (mek.size() >= zro.size()) {
int ret = ask("1x1x");
if (ret == 0) classify("11");
else if (ret == 1) classify("10");
else if (ret == 2) classify("01");
else classify("00");
} else {
int ret = ask("0x0x");
if (ret == 0) classify("00");
else if (ret == 1) classify("01");
else if (ret == 2) classify("10");
else classify("11");
}
}
}
while (last < n) {
VI qr;
for (int x : (mek.size() > zro.size() ? mek : zro)) {
qr.pb(x);
qr.pb(last++);
if (last >= n) break;
}
int ret = use_machine(qr);
int urish = (ret+1)/2;
if (mek.size() > zro.size()) {
cnt0 += urish;
if (ret & 1) zro.pb(last-1);
else mek.pb(last-1);
} else {
cnt0 += qr.size()/2 - urish;
if (ret & 1) mek.pb(last-1);
else zro.pb(last-1);
}
if (max(mek.size(), zro.size()) <= LASTLIM && zro.size() >= 3 && mek.size() >= 2 && n >= 1000) {
while (max(mek.size(), zro.size()) <= LASTLIM) expand();
}
}
return cnt0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
4 ms |
472 KB |
Output is correct |
8 |
Correct |
3 ms |
344 KB |
Output is correct |
9 |
Correct |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
3 ms |
344 KB |
Output is correct |
11 |
Correct |
3 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
344 KB |
Output is correct |
13 |
Correct |
3 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
344 KB |
Output is correct |
15 |
Correct |
3 ms |
344 KB |
Output is correct |
16 |
Correct |
3 ms |
344 KB |
Output is correct |
17 |
Correct |
2 ms |
344 KB |
Output is correct |
18 |
Correct |
2 ms |
344 KB |
Output is correct |
19 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
20 |
Correct |
3 ms |
344 KB |
Output is correct |
21 |
Correct |
3 ms |
344 KB |
Output is correct |
22 |
Correct |
4 ms |
448 KB |
Output is correct |
23 |
Correct |
3 ms |
344 KB |
Output is correct |
24 |
Correct |
2 ms |
344 KB |
Output is correct |
25 |
Correct |
3 ms |
344 KB |
Output is correct |
26 |
Correct |
3 ms |
344 KB |
Output is correct |
27 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
28 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
29 |
Correct |
3 ms |
344 KB |
Output is correct |
30 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
31 |
Correct |
3 ms |
344 KB |
Output is correct |
32 |
Correct |
5 ms |
344 KB |
Output is correct |
33 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
34 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
35 |
Correct |
3 ms |
344 KB |
Output is correct |
36 |
Correct |
3 ms |
344 KB |
Output is correct |
37 |
Correct |
3 ms |
344 KB |
Output is correct |
38 |
Correct |
3 ms |
344 KB |
Output is correct |
39 |
Correct |
3 ms |
344 KB |
Output is correct |
40 |
Correct |
3 ms |
344 KB |
Output is correct |
41 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
42 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
43 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
44 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
45 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
46 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
47 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
48 |
Partially correct |
3 ms |
448 KB |
Output is partially correct |
49 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
50 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
51 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
52 |
Partially correct |
3 ms |
600 KB |
Output is partially correct |
53 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
54 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
55 |
Partially correct |
5 ms |
344 KB |
Output is partially correct |
56 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
57 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
58 |
Partially correct |
5 ms |
344 KB |
Output is partially correct |
59 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
60 |
Partially correct |
5 ms |
344 KB |
Output is partially correct |
61 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
62 |
Correct |
0 ms |
344 KB |
Output is correct |
63 |
Correct |
1 ms |
344 KB |
Output is correct |
64 |
Correct |
0 ms |
344 KB |
Output is correct |
65 |
Correct |
0 ms |
344 KB |
Output is correct |
66 |
Correct |
0 ms |
344 KB |
Output is correct |
67 |
Correct |
0 ms |
344 KB |
Output is correct |
68 |
Correct |
0 ms |
344 KB |
Output is correct |
69 |
Correct |
0 ms |
344 KB |
Output is correct |
70 |
Correct |
0 ms |
344 KB |
Output is correct |
71 |
Correct |
0 ms |
344 KB |
Output is correct |
72 |
Correct |
1 ms |
344 KB |
Output is correct |
73 |
Correct |
0 ms |
344 KB |
Output is correct |
74 |
Correct |
0 ms |
344 KB |
Output is correct |
75 |
Correct |
0 ms |
344 KB |
Output is correct |
76 |
Correct |
0 ms |
344 KB |
Output is correct |
77 |
Correct |
0 ms |
344 KB |
Output is correct |
78 |
Correct |
0 ms |
344 KB |
Output is correct |
79 |
Correct |
0 ms |
344 KB |
Output is correct |
80 |
Correct |
0 ms |
344 KB |
Output is correct |
81 |
Correct |
0 ms |
344 KB |
Output is correct |
82 |
Correct |
0 ms |
344 KB |
Output is correct |
83 |
Correct |
0 ms |
412 KB |
Output is correct |
84 |
Correct |
0 ms |
344 KB |
Output is correct |
85 |
Correct |
0 ms |
344 KB |
Output is correct |
86 |
Correct |
0 ms |
344 KB |
Output is correct |
87 |
Correct |
0 ms |
344 KB |
Output is correct |
88 |
Correct |
0 ms |
344 KB |
Output is correct |
89 |
Correct |
0 ms |
344 KB |
Output is correct |
90 |
Correct |
0 ms |
344 KB |
Output is correct |
91 |
Correct |
0 ms |
344 KB |
Output is correct |