1293 2022. 03. 30 16:05:09 k_balint Nemzetközi Rántott Hús Fesztivál cpp14 Elfogadva 100/100 120ms 38180 KiB 
#include <bits/stdc++.h>
using namespace std;

int n;
string s;
int suf[1000006];
int ans[1000006];
int best[1000006];
stack<int> st;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>s;

    for(int i=n-1;i>=0;i--){
        if(s[i]=='H'){
            best[i]=i;
            st.push(i);
        }
        else{
            if(!st.empty()) st.pop();
            best[i]=st.empty()?n:st.top();
        }
    }

    int h=0,m=0,mh=0;
    for(int i=n-1;i>=0;i--){
        suf[i]=suf[i+1];
        if(s[i]=='H') ++h;
        else if(s[i]=='K'){
            if(h){
                --h; suf[i]++;
            }
            else if(mh){
                ++m; --mh;
            }
            else if(m){
                --m; suf[i]++;
            }
        }
        else{
            if(h){
                --h; ++mh;
                suf[i]++;
            }
            else{
                ++m;
            }
        }
        ans[i]=suf[i]+m/2;
    }

    for(int i=0;i<n;i++){
        if(best[i] != n){
            cout << (best[i]-i)/2 << ' ';
        }

        else{
            cout << ans[i] << ' ';
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 1832 KiB
2 Elfogadva 2ms 1980 KiB
subtask2 7/7
3 Elfogadva 1ms 1880 KiB
4 Elfogadva 1ms 1908 KiB
subtask3 9/9
5 Elfogadva 2ms 2092 KiB
6 Elfogadva 2ms 2012 KiB
7 Elfogadva 2ms 2012 KiB
subtask4 14/14
8 Elfogadva 101ms 28540 KiB
9 Elfogadva 108ms 29584 KiB
10 Elfogadva 104ms 30564 KiB
11 Elfogadva 108ms 31532 KiB
12 Elfogadva 97ms 31448 KiB
13 Elfogadva 97ms 32412 KiB
14 Elfogadva 104ms 32296 KiB
15 Elfogadva 101ms 32752 KiB
subtask5 11/11
16 Elfogadva 1ms 7116 KiB
17 Elfogadva 1ms 7124 KiB
18 Elfogadva 1ms 7124 KiB
subtask6 29/29
19 Elfogadva 2ms 7316 KiB
20 Elfogadva 2ms 7324 KiB
21 Elfogadva 2ms 7328 KiB
22 Elfogadva 1ms 7336 KiB
subtask7 30/30
23 Elfogadva 120ms 33772 KiB
24 Elfogadva 119ms 33172 KiB
25 Elfogadva 114ms 33560 KiB
26 Elfogadva 114ms 33188 KiB
27 Elfogadva 119ms 33016 KiB
28 Elfogadva 119ms 33720 KiB
29 Elfogadva 109ms 34696 KiB
30 Elfogadva 114ms 34612 KiB
31 Elfogadva 115ms 34884 KiB
32 Elfogadva 116ms 33416 KiB
33 Elfogadva 104ms 34400 KiB
34 Elfogadva 108ms 33912 KiB
35 Elfogadva 104ms 34008 KiB
36 Elfogadva 103ms 34268 KiB
37 Elfogadva 98ms 35232 KiB
38 Elfogadva 101ms 36220 KiB
39 Elfogadva 107ms 37208 KiB
40 Elfogadva 108ms 38180 KiB