Submission #354245

#TimeUsernameProblemLanguageResultExecution timeMemory
354245juggernautCounting Mushrooms (IOI20_mushrooms)C++14
100 / 100
12 ms500 KiB
#include"mushrooms.h" #ifndef EVAL #include"stub.cpp" #endif #include<bits/stdc++.h> using namespace std; int count_mushrooms(int n){ vector<int>a,b; a.push_back(0); int id=1; while(max(a.size(),b.size())<100&&id<n){ if(a.size()>=3&&b.size()>=2&&id+4<n){ int ans1=use_machine({a[0],id,a[1],id+1,a[2],id+2}); if(ans1&1)b.push_back(id+2); else a.push_back(id+2); ans1>>=1; if(ans1==0){ a.push_back(id); a.push_back(id+1); id+=3; }else if(ans1==2){ b.push_back(id); b.push_back(id+1); id+=3; }else{ int ans2=use_machine({b[0],id,b[1],a[0],id+1,a[1],id+3,a[2],id+4})-1; if(ans2&1)b.push_back(id+4); else a.push_back(id+4); ans2>>=1; if(ans2&1)b.push_back(id+3); else a.push_back(id+3); ans2>>=1; if(ans2&1){ a.push_back(id); b.push_back(id+1); }else{ b.push_back(id); a.push_back(id+1); } id+=5; } }else if(b.size()>=3&&a.size()>=2&&id+4<n){ int ans1=use_machine({b[0],id,b[1],id+1,b[2],id+2}); if(ans1&1)a.push_back(id+2); else b.push_back(id+2); ans1>>=1; if(ans1==0){ b.push_back(id); b.push_back(id+1); id+=3; }else if(ans1==2){ a.push_back(id); a.push_back(id+1); id+=3; }else{ int ans2=use_machine({a[0],id,a[1],b[0],id+1,b[1],id+3,b[2],id+4})-1; if(ans2&1)a.push_back(id+4); else b.push_back(id+4); ans2>>=1; if(ans2&1)a.push_back(id+3); else b.push_back(id+3); ans2>>=1; if(ans2&1){ b.push_back(id); a.push_back(id+1); }else{ a.push_back(id); b.push_back(id+1); } id+=5; } }else if(a.size()>=2&&id+1<n){ int ans=use_machine({a[0],id,a[1],id+1}); if(ans&1)b.push_back(id+1); else a.push_back(id+1); ans>>=1; if(ans&1)b.push_back(id); else a.push_back(id); id+=2; }else if(b.size()>=2&&id+1<n){ int ans=use_machine({b[0],id,b[1],id+1}); if(ans&1)a.push_back(id+1); else b.push_back(id+1); ans>>=1; if(ans&1)a.push_back(id); else b.push_back(id); id+=2; }else{ if(use_machine({0,id}))b.push_back(id); else a.push_back(id); id++; } } int res=(int)a.size(); while(id<n){ if(a.size()>b.size()){ vector<int>v; for(int i=0;i<a.size()&&id<n;i++){ v.push_back(a[i]); v.push_back(id++); } int ans=use_machine(v); if(ans&1)b.push_back(v.back()); else a.push_back(v.back()); ans++; ans>>=1; res+=(int(v.size())>>1)-ans; }else{ vector<int>v; for(int i=0;i<b.size()&&id<n;i++){ v.push_back(b[i]); v.push_back(id++); } int ans=use_machine(v); if(ans&1)a.push_back(v.back()); else b.push_back(v.back()); ans++; ans>>=1; res+=ans; } } return res; }

Compilation message (stderr)

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