Submission #927265

#TimeUsernameProblemLanguageResultExecution timeMemory
927265velislavgarkovCounting Mushrooms (IOI20_mushrooms)C++14
92.62 / 100
6 ms712 KiB
#include "mushrooms.h" #include <iostream> #include <vector> #include <cmath> using namespace std; int BUCK; vector <int> br[2], mach; int find_eq(int n) { bool fl=false; int start=3, gr=2*BUCK; if (n<=300) { fl=true; gr=n; } for (int i=3;i<gr;i+=2) { if (i==n-1) { start=n-1; break; } int type; if (br[0].size()>1) type=0; else type=1; int s=use_machine({i,br[type][0],i+1,br[type][1]}); if (s==0) { br[type].push_back(i); br[type].push_back(i+1); } else if (s==1) { br[!type].push_back(i); br[type].push_back(i+1); } else if (s==2) { br[type].push_back(i); br[!type].push_back(i+1); } else { br[!type].push_back(i); br[!type].push_back(i+1); } start=i+2; //if (br[0].size()>BUCK || br[1].size()>BUCK) break; } if (start==n-1) { if (!use_machine({0,n-1})) br[0].push_back(n-1); else br[1].push_back(n-1); } if (fl) start=-1; return start; } int count_mushrooms(int n) { br[0].push_back(0); if (!use_machine({0,1})) br[0].push_back(1); else br[1].push_back(1); if (n==2) return br[0].size(); if (!use_machine({0,2})) br[0].push_back(2); else br[1].push_back(2); if (n==3) return br[0].size(); BUCK=sqrt(n/3); int start=find_eq(n); if (start==-1) return br[0].size(); int cur, last; if (br[0].size()>=br[1].size()) cur=0; else cur=1; int ans=br[0].size(); for (int i=start;i<n;i+=last) { if (!mach.empty()) mach.clear(); for (int j=0;j<br[cur].size() && i+j<n;j++) { mach.push_back(i+j); mach.push_back(br[cur][j]); } int s=use_machine(mach); last=br[cur].size(); if (s%2==0) br[cur].push_back(i); else br[!cur].push_back(i); if (cur==1) ans+=(s+1)/2; else ans+=mach.size()/2-(s+1)/2; if (br[0].size()>=br[1].size()) cur=0; else cur=1; } return ans; }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j=0;j<br[cur].size() && i+j<n;j++) {
      |                      ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...