#include "mushrooms.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define pb push_back
using namespace std;
const int maxn = 20000;
vi shroom[2] = {{0},{}};
int uses = 0;
int type[maxn] = {0};
void status(int x, int count) {
cout << "found " << x << " shrooms in " << count << " moves\n";
}
void found(int ind, int val) {
type[ind] = val;
shroom[val].pb(ind);
}
void start(int sec) {
//test A_
vi test = {0,sec};
int res = use_machine(test);
++uses;
found(sec,res);
}
void start2(vi probe) {
//test A_A_
vi test;
int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
int opp = !cur;
for (int i=0; i<2; ++i) {
test.pb(shroom[cur][i]);
test.pb(probe[i]);
}
int res = use_machine(test);
++uses;
int l = probe[0], r = probe[1];
if (res%2 == 0) {
found(r,cur);
} else {
found(r,opp);
--res;
}
if (res == 0) {
found(l,cur);
} else {
found(l,opp);
}
}
int quad(vi probe) {
//test A_A_A_A_
vi test;
int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
int opp = !cur;
int k = probe.size();
for (int i=0; i<k; ++i) {
test.pb(shroom[cur][i]);
test.pb(probe[i]);
}
int res = use_machine(test);
++uses;
int last = probe[k-1];
if (res%2 == 0) {
found(last,cur);
} else {
found(last,opp);
--res;
}
if (res == 0) {
for (int i=0; i<k-1; ++i) {
found(probe[i],cur);
}
} else if (res == 6) {
for (int i=0; i<k-1; ++i) {
found(probe[i],opp);
}
}
return res;
}
void test1(vi probe) {
//test A_A_A_A_ while we have less than 2 B's
int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
int opp = !cur;
int res = quad(probe);
int l = probe[0], m = probe[1], r = probe[2];
if (res == 2) {
vi subtest = {l,m};
start2(subtest);
if (type[l] == cur && type[m] == cur) {
found(r, opp);
} else {
found(r,cur);
}
} else if (res == 4) {
vi subtest = {l,m};
start2(subtest);
if (type[l] == opp && type[m] == opp) {
found(r,cur);
} else {
found(r,opp);
}
}
}
void subtest2(vi probe, int cur) {
//test A_A__B if we know probe is a permutation of (ABB)
//test B_B__A if (AAB)
//future george here: YOU FORGOT THE FREE SHROOM
vi test;
int opp = !cur;
int l = probe[0], m = probe[1], r = probe[2], rr = probe[3];
test = {shroom[cur][0], l, shroom[cur][1], m, r, shroom[opp][0], rr};
int res = use_machine(test);
++uses;
if (res%2 == 0) {
found(rr,cur);
--res;
} else {
found(rr,opp);
}
if (res == 1) {
found(l,cur);
found(m,opp);
found(r,opp);
} else if (res == 3) {
found(l,opp);
found(m,cur);
found(r,opp);
} else if (res == 5) {
found(l,opp);
found(m,opp);
found(r,cur);
}
return;
}
void test2(vi probe) {
//test A_A_A_A_ when we already have 2 B's
//future george here: YOU FORGOT THE FREE SHROOM
vi test = probe;
test.pop_back();
int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
int opp = !cur;
int res = quad(test);
test.pop_back();
test.pb(probe.back());
if (res == 2) {
subtest2(test, opp);
} else if (res == 4) {
subtest2(test, cur);
}
}
int test3(vi probe) {
//test A_A_A_......A_A_
vi test;
int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
int opp = !cur;
int k = probe.size();
for (int i=0; i<k; ++i) {
test.pb(shroom[cur][i]);
test.pb(probe[i]);
}
int res = use_machine(test);
++uses;
int last = probe[k-1];
if (res%2 == 0) {
found(last,cur);
} else {
found(last,opp);
--res;
}
int numcur = res/2;
if (cur == 0) {
return k-1-numcur;
}
return numcur;
}
int count_mushrooms(int n) {
int count_a = 0;
int magic = 90;
for (int i=0; i<n; ++i) {
type[i] = -1;
}
if (n <= 221) {
for (int i = 1; i<n; ++i) {
start(i);
}
return shroom[0].size();
}
int ind = 1;
while (shroom[0].size() < 2 && shroom[1].size()<2) {
start(ind);
++ind;
}
while (shroom[0].size() < 4 && shroom[1].size()<4) {
vi probe = {ind, ind+1};
start2(probe);
ind +=2;
}
int cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
int opp = !cur;
while (shroom[opp].size() < 2 && shroom[cur].size() < magic) {
vi probe;
for (int i=0; i<4; ++i) {
probe.pb(ind);
++ind;
}
test1(probe);
}
cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
opp = !cur;
while (shroom[cur].size() < magic) {
vi probe;
for (int i=0; i<5; ++i) {
probe.pb(ind);
++ind;
}
test2(probe);
cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
opp = !cur;
}
while (ind != n) {
cur = (shroom[0].size() >= shroom[1].size()) ? 0 : 1;
opp = !cur;
int s = shroom[cur].size();
int cap = min(s, n-ind);
vi probe;
for (int i=0; i<cap; ++i) {
probe.pb(ind);
++ind;
}
count_a += test3(probe);
}
return count_a + shroom[0].size();
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:211:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
211 | while (shroom[opp].size() < 2 && shroom[cur].size() < magic) {
| ~~~~~~~~~~~~~~~~~~~^~~~~~~
mushrooms.cpp:221:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
221 | while (shroom[cur].size() < magic) {
| ~~~~~~~~~~~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
380 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
4 ms |
336 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
336 KB |
Answer is not correct. |
| 7 |
Halted |
0 ms |
0 KB |
- |
