Submission #720560

#TimeUsernameProblemLanguageResultExecution timeMemory
720560bin9638Counting Mushrooms (IOI20_mushrooms)C++17
80.71 / 100
11 ms444 KiB
#include <bits/stdc++.h> #ifndef SKY #include "mushrooms.h" #endif // SKY using namespace std; #define N 100010 #define ll long long #define fs first #define sc second #define ii pair<int,int> #define pb push_back #ifdef SKY int type[N]; int use_machine(vector<int>s) { int res=0; for(int i=0;i<s.size()-1;i++) res+=(type[s[i]]!=type[s[i+1]]); return res; } #endif // SKY int n; vector<int>A,B; int count_mushrooms(int cc) { n=cc; A.clear(); B.clear(); A.pb(0); int res=1; for(int i=1;i<n;) { if(A.size()>=B.size()) { vector<int>hoi; int cnt=0; for(int j=i;j<min(n,i+(int)A.size());j++) { cnt++; hoi.pb(j); hoi.pb(A[j-i]); } int val=(cnt*2-1-use_machine(hoi)); res+=((val+1)/2); if(val&1) A.pb(i); else B.pb(i); i+=(A.size()-(val&1)); }else { vector<int>hoi; int cnt=0; for(int j=i;j<min(n,i+(int)B.size());j++) { hoi.pb(j); hoi.pb(B[j-i]); cnt++; } int val=(cnt*2-1-use_machine(hoi)); res+=(cnt-((val+1)/2)); if(val&1) B.pb(i); else A.pb(i); i+=(B.size()-(val&1)); } // cout<<res<<" "<<i<<endl; } return res; } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; for(int i=0;i<n;i++) cin>>type[i]; cout<<count_mushrooms(n); return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...