# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1066205 | Ahmed57 | Counting Mushrooms (IOI20_mushrooms) | C++17 | 6 ms | 600 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;
#include "mushrooms.h"
int count_mushrooms(int n){
int B = 273;
vector<int> BS[2];
int cnt = 0;
vector<int> pending;
BS[0].push_back(0);
for(int i = 1;i<min(n,3);i++){
if(use_machine({0,i})){
BS[1].push_back(i);
}else {
BS[0].push_back(i);
}
}
int la = 2;
for(int i = 3;i+1<min(n,B);i+=2){
la = i+1;
if(BS[0].size()>1){
//A
int an = use_machine({BS[0][0],i,BS[0][1],i+1});
if(an==0){
BS[0].push_back(i);
BS[0].push_back(i+1);
continue;
}if(an==1){
BS[0].push_back(i);
BS[1].push_back(i+1);
continue;
}if(an==2){
BS[1].push_back(i);
BS[0].push_back(i+1);
continue;
}else{
BS[1].push_back(i);
BS[1].push_back(i+1);
continue;
}
}else{
int an = use_machine({BS[1][0],i,BS[1][1],i+1});
if(an==0){
BS[1].push_back(i);
BS[1].push_back(i+1);
continue;
}if(an==1){
BS[1].push_back(i);
BS[0].push_back(i+1);
continue;
}if(an==2){
BS[0].push_back(i);
BS[1].push_back(i+1);
continue;
}else{
BS[0].push_back(i);
BS[0].push_back(i+1);
continue;
}
}
}
if(la+1<min(n,B)){
if(use_machine({0,la+1})){
BS[1].push_back(la+1);
}else BS[0].push_back(la+1);
}
cnt = BS[0].size();
int sz = max(BS[0].size(),BS[1].size());
vector<int> bs;
bool As = 0;
if(BS[0].size()>BS[1].size()){
As = 1;
bs = BS[0];
}else bs = BS[1];
for(int i = B;i<n;i+=sz){
int xd = i;
vector<int> lol;
int nah = 0;
int last = -1;
for(int j = i;j<min(n,i+sz);j++){
nah++;
lol.push_back(bs[j-i]);
lol.push_back(j);
last = j;
}
int ans = use_machine(lol);
if(ans%2){
if(As==0){
cnt++;
BS[0].push_back(last);
}else BS[1].push_back(last);
ans--;
}else{
if(As==1){
cnt++;
BS[0].push_back(last);
}else BS[1].push_back(last);
}
ans/=2;
nah--;
if(As==0)cnt+=ans;
else cnt+=nah-ans;
}
return cnt;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |