#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<int> state;
int flip(int k){
if (k==2) return 1;
return 2;
}
pii check(int i, int j){
if(state[0]==state[1] && state[1]==state[2]){
int x = use_machine({0, i, 1, 2, j});
if(state[0]==1)return {((x&2)>>1)+1, (x&1)+1};
else return {flip(((x&2)>>1)+1), flip((x&1)+1)};
}
if(state[0]==state[1]){
int x = use_machine({0, i, 1, 2, j})-1;
if(state[0]==1)return {((x&2)>>1)+1, flip((x&1)+1)};
else return {flip(((x&2)>>1)+1), (x&1)+1};
}
if(state[1]==state[2]){
int x = use_machine({1, i, 2, 0, j})-1;
//cout << x << '\n';
//cout << 1 << ' ' << i << ' '<< 2 << ' ' << 0 << ' ' << j << '\n';
if(state[1]==1)return {((x&2)>>1)+1, flip((x&1)+1)};
else return {flip(((x&2)>>1)+1), (x&1)+1};
}
if(state[0]==state[2]){
int x = use_machine({0, i, 2, 1, j})-1;
if(state[0]==1)return {((x&2)>>1)+1, flip((x&1)+1)};
else return {flip(((x&2)>>1)+1), (x&1)+1};
}
}
int test(vector<int> tester, vector<int> tested, int tri){
vector<int> cun;
for(int i = 0;i<tester.size();i++){
cun.push_back(tester[i]);
cun.push_back(tested[i]);
}
auto x = use_machine(cun);
int cn=x/2+(x&1);
if(tri==2)cn=tester.size()-cn;
return cn;
}
const int cut=200;
int count_mushrooms(int n) {
state.assign(n, 0);
//0 not known 1 A 2 B
state[0]=1;
int second = use_machine({0, 1})+1;
state[1]=second;
if(n==2)return 1+(second-1)^1;
int third = use_machine({0, 2})+1;
state[2]=third;
if (n<=400){
int res = 1+(second==1 ? 1:0) + (third==1 ? 1:0);
//cout << "res: " << res << '\n';
if (!(n&1))res+=use_machine({0, n-1})^1;
for(int test=4;test<n;test+=2){
auto x = check(test-1, test);
//cout << x.first << ' ' << x.second << '\n';
if(x.first==1)res++;
if(x.second==1)res++;
}
return res;
}
else{
for(int tes=4;tes<cut;tes+=2){
auto x = check(tes-1, tes);
state[tes-1]=x.first;
state[tes]=x.second;
}
}
vector<int> as, bs;
int res = 0;
for(int i =0;i<cut;i++){
if (state[i]==1){
as.push_back(i);
res++;
}
else bs.push_back(i);
}
int ntt=1;
if (as.size()<bs.size()){
swap(as, bs);
ntt=2;
}
vector<int> uki;
for(int i = 0;i<n;i++){
if(state[i]==0)uki.push_back(i);
}
while(uki.size()!=0){
if (uki.size()>=as.size()){
vector<int> tes;
for(int i = 0;i<as.size();i++){
tes.push_back(uki.back());
uki.pop_back();
}
res+=test(as, tes, ntt);
}
else{
while(uki.size()<as.size()){
as.pop_back();
res+=test(as, uki, ntt);
}
uki={};
}
}
return res;
}
Compilation message (stderr)
mushrooms.cpp: In function 'pii check(int, int)':
mushrooms.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
34 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |