# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1080908 | UmairAhmadMirza | Counting Mushrooms (IOI20_mushrooms) | C++17 | 2 ms | 444 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|---|---|---|---|
Fetching results... |