/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int use_machine(vector<int>x);
int count_mushrooms(int n){
if(n<=226){
int ret=1;
for(int i=1;i<n;i++){
ret+=1-use_machine({0,i});
}
return ret;
}
int ret=0,k=94;
vector<int>v[2];
v[0].push_back(0);
for(int i=1;i<=2;i++){
if(use_machine({0,i})==0)v[0].push_back(i);
else v[1].push_back(i);
}
bool typ;
int x,y;
if(v[0].size()>=2){
typ=0;
x=v[0][0];y=v[0][1];
}
else{
typ=1;
x=v[1][0];y=v[1][1];
}
for(int i=3;i<=2*k-2;i+=2){
int h=use_machine({x,i,y,i+1});
if(h==0){
v[typ].push_back(i);
v[typ].push_back(i+1);
}
if(h==1){
v[typ^1].push_back(i);
v[typ].push_back(i+1);
}
if(h==2){
v[typ].push_back(i);
v[typ^1].push_back(i+1);
}
if(h==3){
v[typ^1].push_back(i);
v[typ^1].push_back(i+1);
}
}
auto f=[&](int l,int r){
vector<int>p;
vector<int>&g=(v[0].size()>v[1].size()?v[0]:v[1]);
if(v[0].size()>v[1].size())typ=0;
else typ=1;
assert(r-l+1<=(int)g.size());
for(int i=l;i<=r;i++){
p.push_back(i);
p.push_back(g[i-l]);
}
int u=use_machine(p);
if(u&1)v[typ^1].push_back(l);
else v[typ].push_back(l);
u=(u+1)/2;
if(typ)return u;
else return r-l+1-u;
};
ret=(int)v[0].size();
int mx=max(v[0].size(),v[1].size());
vector<bool>ok(n);
for(int i=0;i<=2*k-2;i++)ok[i]=1;
for(int i=2*k-1;i<n;i+=mx){
ret+=f(i,min(i+mx-1,n-1));
for(int j=i;j<=min(i+mx-1,n-1);j++)ok[j]=1;
mx=max(v[0].size(),v[1].size());
}
int cnt=0;
for(int i=0;i<n;i++)cnt+=ok[i];
assert(cnt==n);
return ret;
}
| # |
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 |
1 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 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
