#include <bits/stdc++.h>
using namespace std;
int const N=20005;
int const H=141;
int use_machine(vector<int> x);
int solve(int n){
vector<int> A,B;
A.push_back(0);
vector<int> q;
q.push_back(0);
for(int i=1;i<n;i++){
q.push_back(i);
if(use_machine(q))
B.push_back(i);
else
A.push_back(i);
q.pop_back();
}
return int(A.size());
}
int count_mushrooms(int n){
if(n<=282)
return solve(n);
vector<int> A,B;
A.push_back(0);
vector<int> q;
q.push_back(0);
for(int i=1;i<n;i++){
q.push_back(i);
if(use_machine(q))
B.push_back(i);
else
A.push_back(i);
q.pop_back();
if(A.size()>=2 || B.size()>=2)
break;
}
bool bl=0;
if(A.size()<B.size()){
swap(A,B);
bl=1;
}
for (int i = (A.size()+B.size()); i < n; i+=2)
{
q.clear();
q.push_back(A[0]);
q.push_back(i);
q.push_back(A[1]);
q.push_back(i+1);
int v=use_machine(q);
if(v%2==0)
A.push_back(i+1);
else
B.push_back(i+1);
if(v>=2)
B.push_back(i);
else
A.push_back(i);
if(A.size()>=H || B.size()>=H)
break;
}
if(bl){
bl=0;
swap(A,B);
}
if(A.size()<B.size()){
bl=1;
swap(A,B);
}
int cntA=A.size(),cntB=B.size();
int h=A.size();
for(int i=(A.size()+B.size());i<n;i+=h){
vector<int> q;
for(int j=i;j<min(i+h,n);j++){
q.push_back(A[j-i]);
q.push_back(j);
}
int v=use_machine(q)+1;
if(v%2){
A.push_back(min(n,i+h-1));
h++;
}
cntB+=v/2;
}
cntA=n-cntB;
if(bl)
swap(cntB,cntA);
return cntA;
}
| # |
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 |
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 |
2 ms |
444 KB |
Answer is not correct. |
| 7 |
Halted |
0 ms |
0 KB |
- |
