Submission #474687

#TimeUsernameProblemLanguageResultExecution timeMemory
474687vincent97198JJOOII 2 (JOI20_ho_t2)C++14
100 / 100
9 ms3028 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n,k; cin >> n >> k; string s; cin >> s; vector<int> pos(n),near_O(n),near_I(n); int J_r=-1,J_cnt=0,O_r=-1,O_cnt=0,I_r=-1,I_cnt=0; for(int i=0;i<n;++i){ while(J_cnt<k && J_r<n){ ++J_r; if(s[J_r]=='J') ++J_cnt; } while(O_cnt<k && O_r<n){ ++O_r; if(s[O_r]=='O') ++O_cnt; } while(I_cnt<k && I_r<n){ ++I_r; if(s[I_r]=='I') ++I_cnt; } if(s[i]=='J'){ if(J_cnt==k) pos[i]=J_r; else pos[i]=-1; --J_cnt; } else if(s[i]=='O'){ if(O_cnt==k) pos[i]=O_r; else pos[i]=-1; --O_cnt; } else{ if(I_cnt==k) pos[i]=I_r; else pos[i]=-1; --I_cnt; } } int O_is_here=-1,I_is_here=-1; for(int i=n-1;i>=0;--i){ if(s[i]=='O') O_is_here=i; near_O[i]=O_is_here; } for(int i=n-1;i>=0;--i){ if(s[i]=='I') I_is_here=i; near_I[i]=I_is_here; } // for(int i=0;i<n;++i) cout << "pos" << i << ": " << pos[i] << endl; int ans=(1<<30); for(int i=0;i<n;++i){ int tmp=0; if(s[i]=='J'){ if(pos[i]==-1) continue; tmp+=pos[i]-i+1-k; if(near_O[pos[i]]==-1 || pos[near_O[pos[i]]]==-1) continue; tmp+=pos[near_O[pos[i]]]-near_O[pos[i]]+1-k+near_O[pos[i]]-pos[i]-1; if(near_I[pos[near_O[pos[i]]]]==-1 || pos[near_I[pos[near_O[pos[i]]]]]==-1) continue; tmp+=pos[near_I[pos[near_O[pos[i]]]]]-near_I[pos[near_O[pos[i]]]]+1-k+near_I[pos[near_O[pos[i]]]]-pos[near_O[pos[i]]]-1; /* cout << i << " " << near_O[pos[i]] << " " << near_I[pos[near_O[pos[i]]]] << endl; cout << "ww\n"; cout << pos[i] << " " << pos[near_O[pos[i]]] << " " << pos[near_I[pos[near_O[pos[i]]]]] << endl; */ ans=min(ans,tmp); } } if(ans!=(1<<30)) cout << ans << '\n'; else cout << -1 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...