1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin>>n;

    vector<bool> gl;
    char a;
    for(int i = 0; i<n; i++){
        cin>>a;
        if(a=='L'){
            gl.push_back(1);
            continue;
        }
        gl.push_back(0);
    }
    int sl = 0, sr = n;
    for(int i = 0; i<n; i++){
        if(!gl[i]) break;
        sl++;
    }

    for(int i = n-1; i>=0; i--){
        if(gl[i]) break;
        sr--;
    }

    //cout<<sl<<" : "<<sr<<endl;

    vector<int> prefixSumL, prefixSumR;
    prefixSumL.assign(n+1, 0);
    prefixSumR.assign(n+1, 0);

    for(int i = 0; i<n; i++){
        prefixSumL[i+1] = prefixSumL[i];
        prefixSumR[i+1] = prefixSumR[i];
        if(i<sl or i>=sr) continue;
        prefixSumL[i+1] = prefixSumL[i]+gl[i];
        prefixSumR[i+1] = prefixSumR[i]+(!gl[i]);
    }

    int tmp1, tmp2;
    for(int i = 0; i<n; i++){
        if(gl[i]){
            tmp1 = prefixSumR[i+1];
            tmp2 = prefixSumL.back() - prefixSumL[i+1];
            if(tmp1<=tmp2){
                cout<<tmp1*2<<" ";
                continue;
            }
            cout<<tmp2*2+1<<" ";
            continue;
        }

        tmp1 = prefixSumR[i];
        tmp2 = prefixSumL.back() - prefixSumL[i+1];
        if(tmp2<=tmp1){
            cout<<tmp2*2<<" ";
            continue;
        }
        cout<<tmp1*2+1<<" ";
        continue;
    }

    return 0;
}