| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1064442 | new_acc | Counting Mushrooms (IOI20_mushrooms) | C++14 | 0 ms | 0 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 "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int count_mushrooms(int n){
int c1 = use_machine({0,1});
if(n==2) return 2-c1;
int c2 = use_machine({0,2});
if(n==3) return 3-c1-c2;
vi x[2];
x[0].push_back(0);
if(c1) x[1].push_back(1);
else x[0].push_back(1);
if(c2) x[1].push_back(2);
else x[0].push_back(2);
int g=3;
bool ok=1;
int a=0,b=0;
if(!c1) a=0,b=1;
else{
if(!c2) a=0,b=2;
else ok^=1,a=1,b=2;
}
for(int i=3;i<n-1;i+=2){
if(x[0].size()>=50 and x[1].size()>=50 and
abs(x[1].size()-x[0].size())<10) break;
if(x[0].size()>=85 or x[1].size()>=85) break;
int c3=use_machine({i,a,i+1,b});
if((c3&1)) x[ok].push_back(i);
else x[ok^1].push_back(i);
if((c3&2)) x[ok].push_back(i+1);
else x[ok^1].push_back(i+1);
g=i+2;
}
int res=x[0].size();
for(int i=g;i<n;){
vi pom=x[0];
bool odw=0;
if(x[1].size()>x[0].size()){
odw=1;
pom=x[1];
}
vi pom2;
int i2;
for(i2=0;i2+i<n and i2<(int)pom.size();i2++){
pom2.push_back(pom[i2]);
pom2.push_back(i+i2);
}
i+=i2;
int c3=use_machine(pom2);
if(!odw) c3=pom2.size()-1-c3;
if(c3%2==1) x[0].push_back(i-1);
else x[1].push_back(i-1);
res+=(c3+1)/2;
}
return res;
}