#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int B = 100;
//const int B = 3;
vector<int> perm;
int ask(vector<int> v){
for(auto &i:v)i = perm[i];
return use_machine(v);
}
int count_mushrooms(int n) {
if(n<=B*3){
int ans = 1;
for(int i = 1;i<n;i++){
int re = use_machine(vector<int>({0,i}));
if(!re)ans++;
}
return ans;
}
srand(time(NULL));
for(int i = 0;i<n;i++)perm.push_back(i);
random_shuffle(perm.begin()+1,perm.end());
vector<int> v[2];
v[0].push_back(0);
int nxt = 1;
for(int i = 1;max(v[0].size(),v[1].size())<B;i++){
int re = ask(vector<int>({0,i*3-2,i*3-1,i*3}));
if(re == 0){
v[0].push_back(i*3-2);
v[0].push_back(i*3-1);
v[0].push_back(i*3);
}
else if(re == 3){
v[1].push_back(i*3-2);
v[1].push_back(i*3-1);
v[1].push_back(i*3);
}
else if(re == 1){
v[1].push_back(i*3);
v[1].push_back(i*3-1);
re = ask(vector<int>({0,i*3-2}));
if(re == 0)v[0].push_back(i*3-2);
else v[1].push_back(i*3-2);
}
else if(re == 2){
v[0].push_back(i*3);
int re = ask(vector<int>({0,i*3-2}));
if(re == 0){
v[0].push_back(i*3-2);
v[1].push_back(i*3-1);
}
else{
v[1].push_back(i*3-2);
v[0].push_back(i*3-1);
}
}
nxt = i*3+1;
}
int dir = (v[0].size()<v[1].size());
int cnt[2] = {v[0].size(),v[1].size()};
/*
cerr<<"DIR: "<<dir<<endl;for(auto &i:v[dir])cerr<<i<<',';cerr<<endl;
cerr<<"NXT: "<<nxt<<endl;
*/
for(int i = nxt;i<n;i+=v[dir].size()){
vector<int> vv;
for(int j = i;j<min(n,i+(int)v[dir].size());j++)vv.push_back(j);
//cerr<<"VV: ";for(auto &j:vv)cerr<<j<<',';cerr<<endl;
vector<int> req;
for(int j = 0;j<vv.size();j++){
req.push_back(v[dir][j]);
req.push_back(vv[j]);
}
//cerr<<nxt<<','<<vv.size()<<":"<<endl;for(auto &j:req)cerr<<j<<',';cerr<<endl;
int re = ask(req);
if(re&1)re++;
re>>=1;
cnt[dir^1] += re;
cnt[dir] += vv.size()-re;
}
return cnt[0];
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:64:25: warning: narrowing conversion of 'v[0].std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
64 | int cnt[2] = {v[0].size(),v[1].size()};
| ~~~~~~~~~^~
mushrooms.cpp:64:37: warning: narrowing conversion of 'v[1].std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
64 | int cnt[2] = {v[0].size(),v[1].size()};
| ~~~~~~~~~^~
mushrooms.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j = 0;j<vv.size();j++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
1 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Answer is not correct. |
| 7 |
Halted |
0 ms |
0 KB |
- |
