/*
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=137;
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({i,x,i+1,y});
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);
}
}
vector<int>g;
if(v[0].size()>=k){
typ=0;
for(int i=0;i<k;i++)g.push_back(v[0][i]);
}
else{
typ=1;
for(int i=0;i<k;i++)g.push_back(v[1][i]);
}
auto f=[&](int l,int r){
vector<int>p;
for(int i=l;i<=r;i++){
p.push_back(i);
p.push_back(g[i-l]);
}
int g=use_machine(p);
g=(g+1)/2;
if(typ)return g;
else return r-l+1-g;
};
ret=(int)v[0].size();
int mx=(int)v[typ].size();
for(int i=2*k-1;i<n;i+=mx){
ret+=f(i,min(i+mx-1,n-1));
}
return ret;
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:56:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
56 | if(v[0].size()>=k){
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
368 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Duplicate value 0 in the query array. |
| 7 |
Halted |
0 ms |
0 KB |
- |
