Submission #1066124

#TimeUsernameProblemLanguageResultExecution timeMemory
1066124Ahmed57Counting Mushrooms (IOI20_mushrooms)C++17
25 / 100
22 ms1004 KiB
#include "bits/stdc++.h" using namespace std; #include "mushrooms.h" int count_mushrooms(int n){ int B = 100; vector<int> BS; int cnt = 0; vector<int> pending; for(int i = 0;i<n;i+=B){ vector<int> v; if(i!=0)v.push_back(0); for(int j = i;j<min(n,i+B);j++)v.push_back(j); if(use_machine(v)==0){ cnt+=(min(i+B,n)-i); continue; } int l = max(1,i) , r =min(n-1,i+B-1) , ans = -1; while(l<=r){ vector<int> v; int mid = (l+r)/2; if(i!=0)v.push_back(0); for(int j = i;j<=mid;j++){ v.push_back(j); } if(use_machine(v)!=0){ ans = mid; r = mid-1; }else l = mid+1; } BS.push_back(ans); for(int j = ans+1;j<min(n,i+B);j++){ pending.push_back(j); } cnt+=ans-i; } int sz = BS.size(); int sz2 = pending.size(); for(int i = 0;i<pending.size();i+=sz){ int xd = i; vector<int> lol; for(int j = i;j<min(sz2,i+sz);j++){ lol.push_back(BS[j-i]); lol.push_back(pending[j]); } int ans = use_machine(lol); if(ans%2){ cnt++; ans--; } ans/=2; cnt+=ans; } return cnt; }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0;i<pending.size();i+=sz){
      |                   ~^~~~~~~~~~~~~~~
mushrooms.cpp:39:13: warning: unused variable 'xd' [-Wunused-variable]
   39 |         int xd = i;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...