#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int k=100;
vector <int> a,b;
int t,res,sz;
int count_mushrooms(int n){
if (n<=227){
for (int i=1;i<n;i++)
res+=1-use_machine({0,i});
return res+1;
}
a.push_back(0);
for (int i=1;i<=k*2;i++){
if (max(a.size(),b.size())==k)
break;
int x=use_machine({0,i});
if (x)
b.push_back(i);
else
a.push_back(i);
}
sz=a.size();
t=(a.size()!=k);
if (a.size()!=k)
swap(a,b);
for (int i=a.size()+b.size();i<n;i+=k*2){
if (i==n-1){
res+=abs(t-use_machine({0,i}));
continue;
}
vector <int> ve;
for (int j=i;j<min(i+k+1,n);j++){
ve.push_back(j);
if (j-i<a.size())
ve.push_back(a[j-i]);
}
int x=use_machine(ve);
if (i==n-2){
res+=x;
continue;
}
int l=ve[0],r=ve.back();
ve.clear();
ve.push_back(l);
for (int j=min(i+k+1,n);j<min(i+k*2,n);j++){
ve.push_back(a[j-i-k-1]);
ve.push_back(j);
}
ve.push_back(min(i+k*2,n)-min(i+k+1,n));
ve.push_back(r);
x+=use_machine(ve);
res+=x/2;
}
return (t?res:n-a.size()-b.size()-res)+sz;
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (j-i<a.size())
| ~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
448 KB |
Duplicate value 99 in the query array. |
| 7 |
Halted |
0 ms |
0 KB |
- |
