Submission #1035388

#TimeUsernameProblemLanguageResultExecution timeMemory
1035388GrayCounting Mushrooms (IOI20_mushrooms)C++17
75.59 / 100
6 ms600 KiB
#include "mushrooms.h" #define ff first #define ss second #define ll int #define ln "\n" using namespace std; int qry=200; int count_mushrooms(int n) { std::vector<int> query; vector<int> as, bs; as.push_back(0); for (ll i=1; i<=min(2, n-1); i++){ query = {0, int(i)}; ll ret = use_machine(query); if (ret==0) as.push_back(i); else bs.push_back(i); } for (ll i=3; i<min(qry+1, n); i+=2){ if (i+1<min(qry+1, n)){ if (as.size()>bs.size()){ query = {i, as[0], i+1, as[1]}; ll ret = use_machine(query); if (ret==0){ as.push_back(i); as.push_back(i+1); }else if (ret==1){ as.push_back(i+1); bs.push_back(i); }else if (ret==2){ as.push_back(i); bs.push_back(i+1); }else{ bs.push_back(i); bs.push_back(i+1); } }else{ query = {i, bs[0], i+1, bs[1]}; ll ret = use_machine(query); if (ret==0){ bs.push_back(i); bs.push_back(i+1); }else if (ret==1){ bs.push_back(i+1); as.push_back(i); }else if (ret==2){ bs.push_back(i); as.push_back(i+1); }else{ as.push_back(i); as.push_back(i+1); } } }else{ query = {0, (int)i}; ll ret = use_machine(query); if (ret==0) as.push_back(i); else bs.push_back(i); } } ll ans=(ll)as.size(); if (as.size()>bs.size()){ for (ll i=min(qry+1, n); i<n; i+=as.size()-1){ query.clear(); for (ll j=0; j<(ll)as.size()-1 and i+j<n; j++){ query.push_back(as[j]); query.push_back(i+j); } query.push_back(as.back()); ll ret = use_machine(query)/2ll; ans+=(query.size()-1)/2-ret; } }else{ for (ll i=min(qry+1, n); i<n; i+=bs.size()-1){ query.clear(); for (ll j=0; j<(ll)bs.size()-1 and i+j<n; j++){ query.push_back(bs[j]); query.push_back(i+j); } query.push_back(bs.back()); ll ret = use_machine(query)/2ll; ans+=ret; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...