#include <bits/stdc++.h>
using namespace std;
int use_machine(vector<int> x);
const int SQRT = 141;
int strat1(int n){
vector<bool> type(n);
{
int t = use_machine({0,1});
if(t==0)type[1]=false;
else type[1]=true;
}
if(n>2){
int t = use_machine({0,2});
if(t==0)type[2]=false;
else type[2]=true;
} else {
return 1 + (int)(type[1]==false);
}
int a,b;bool ty;
if(type[0]==type[1]){
a = 0;
b = 1;
ty = false;
} else if(type[0]==type[2]){
a = 0;
b = 2;
ty = false;
} else {
a = 1;
b = 2;
ty = true;
}
type.emplace_back(false);
for(int i=3;i<n;i+=2){
int curr;
if(i==n-1){
curr = use_machine({a,i,b});
} else {
curr = use_machine({a,i,b,i+1});
}
if(curr&1){
type[i+1] = !ty;
} else type[i+1] = ty;
if(curr&2){
type[i] = !ty;
} else type[i] = ty;
}
int ans = 0;
for(int i=0;i<n;i++)if(type[i]==false)ans++;
return ans;
}
int checked_until = -1;
vector<int> ask(){
vector<bool> type(3*SQRT);
int cnt_false = 1,cnt_true = 0;
{
int t = use_machine({0,1});
if(t==0){type[1]=false;cnt_false++;}
else {type[1]=true;cnt_true++;}
}
{
int t = use_machine({0,2});
if(t==0){type[2]=false;cnt_false++;}
else {type[2]=true;cnt_true++;}
}
int a,b;bool ty;
if(type[0]==type[1]){
a = 0;
b = 1;
ty = false;
} else if(type[0]==type[2]){
a = 0;
b = 2;
ty = false;
} else {
a = 1;
b = 2;
ty = true;
}
type.emplace_back(false);
vector<int> falses;
vector<int> trues;
for(int i=3;i<3*SQRT;i+=2){
int curr = use_machine({a,i,b,i+1});
if(curr&2){
type[i] = !ty;
} else type[i] = ty;
checked_until = i+1;
if(type[i]==false){
if(++cnt_false==SQRT)break;
} else {
if(++cnt_true==SQRT)break;
}
if(curr&1){
type[i+1] = !ty;
} else type[i+1] = ty;
checked_until = i+2;
if(type[i+1]==false){
if(++cnt_false==SQRT)break;
} else {
if(++cnt_true==SQRT)break;
}
}
vector<int> ans;
bool tar;
if(cnt_false==SQRT)tar = false;
else tar = true;
for(int i=0;i<checked_until;i++)if(type[i]==tar)ans.emplace_back(i);
assert(ans.size()==SQRT);
return ans;
}
int count_mushrooms(int n) {
// if(n<=450)return strat1(n);
auto idx = ask();
bool ty = idx.front()!=0;
int ans = 0;
if(ty){
ans = checked_until-SQRT;
for(int i=checked_until;i<n;i+=SQRT){
vector<int> buffer;
for(int j=0;j<SQRT;j++)if(i+j<n)buffer.emplace_back(i+j);
vector<int> query;
query.emplace_back(buffer.front());
auto iter = buffer.begin()+1;
auto iterb = idx.begin();
while(iter!=buffer.end()){
query.emplace_back(*iterb++);
query.emplace_back(*iter++);
}
int t = use_machine(query);t++;t/=2;
ans+=t;
}
} else {
ans = SQRT;
for(int i=checked_until;i<n;i+=SQRT){
vector<int> buffer;
for(int j=0;j<SQRT;j++)if(i+j<n)buffer.emplace_back(i+j);
vector<int> query;
query.emplace_back(buffer.front());
auto iter = buffer.begin()+1;
auto iterb = idx.begin();
while(iter!=buffer.end()){
query.emplace_back(*iterb++);
query.emplace_back(*iter++);
}
int t = use_machine(query);t++;t/=2;
ans+=buffer.size()-t;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Too large array for query. |
| 2 |
Halted |
0 ms |
0 KB |
- |
