#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 = 110;
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);
if (harc[u].size() == 5) {
classify(harc[u]);
break;
}
u = gp[u][ret];
}
};
if (false && n >= 10) {
if (!ask("0x")) {
classify("0");
} else {
classify("1");
if (!ask("0x")) classify("0");
else classify("1");
}
rep(_, 4) {
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 (last <= LASTLIM && zro.size() >= 3 && mek.size() >= 2 && n >= 200) {
while (last <= LASTLIM) expand();
}
}
return cnt0;
}
| # |
Verdict |
Execution time |
Memory |
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 |
Incorrect |
1 ms |
344 KB |
Duplicate value 0 in the query array. |
| 6 |
Halted |
0 ms |
0 KB |
- |
