Left or Right

Author : srikar3010

Required Knowledge : Constructive

Time Complexity : $O(N)$

Editorialist : srikar3010

Approach:

When we break the string into segments like $"RR...RLL...L"$, we can treat each segment independently since there is no interaction between different parts. For example, "RRLRL" can be analyzed as two separate parts: $"RRL"$ and $"RL"$. From here on, we focus only on patterns of the form $"RR...RLL...L"$. After a sufficiently large number of moves $10^{100}$, children will gather at the boundaries, specifically at the $"RL"$ transition, and no children will remain in other positions. Furthermore, children who initially started on even-numbered positions (counted from the left) will never gather with those who started on odd-numbered positions. Instead, children who started at positions with the same parity (even or odd) will all end up at the same final position. Since the number of moves is $10^{100}$, which is even, children originally on even-numbered positions relative to the "R" in the "RL" pair will gather at the "R", and those on even-numbered positions relative to the "L" will gather at the "L" and vice versa.

For the input $"RRRLLL"$, children gather at the boundary where $'R'$ meets $'L'$ (positions $2$ and $3$). Children at even-numbered positions relative to $'R'$ (counting from $0$) will gather at $'R'$ (position $2$), while those at odd-numbered positions relative to $'R'$ will gather at $'L'$ (position $3$). After all moves, the final positions are: $0 \ 0 \ 3 \ 3 \ 0 \ 0$ with $3$ children at positions $2$ and $3$.

Code:

// Author:Srikar
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>    
using namespace std;
// using namespace __gnu_pbds;
#define ll long long
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>pbds;
//find kth element *pbds.find_by_order(k);
//find no of elements smaller than x *pbds.order_of_key(x);
#define ld long double
#define modulo 1000000007
#define vec vector<ll>
#define f(j,n) for(int i=j; i<n; i++)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define alice cout<<"Alice"<<endl;
#define bob cout<<"Bob"<<endl;
#define umpl unordered_map<ll,ll>
#define mpl map<ll,ll>
#define umpc unordered_map<char,ll>
#define mpc map<char,ll>

// *******************************TEMPLATE*****************************

template<class T>
void print(T &a){ cout<<a<<" "; };
template<class T>
void printnxt(T &a){ cout<<a<<endl; };
template<class T1>
ll sb(T1 &a){return __builtin_popcount(a);}
template<class T1>
ll par(T1 &a){return __builtin_parityll(a);}
template<class T1>
ll lz(T1 &a){return __builtin_clzll(a);}
template<class T1>
ll tz(T1 &a){return __builtin_ctzll(a);}
template<class T3>
vector<T3> sorta(vector<T3>&a) { sort(a.begin(),a.end()); return a;}
template<class T3>
ll maxele(vector<T3>&a) { return *max_element(a.begin(),a.end());}
template<class T3>
ll minele(vector<T3>&a) { return *min_element(a.begin(),a.end());}
template<class T3>
vector<T3> sortd(vector<T3>&a) { sort(a.begin(),a.end(),greater<ll>()); return a;}
template<class T3>
vector<T3> rev(vector<T3>&a) { reverse(a.begin(),a.end()); return a;}
template<class T3>
void printv(vector<T3>&a) { for(auto i:a) cout<<i<<" "; cout<<endl;}
template<class T3>
void freq(vector<T3>&a,map<T3,ll>&m){ for(auto& i:a) m[i]++; }
template <class T>
void input(vector<T>&v){ for(auto &val:v) cin>>val; }
template<typename T2>
vector<T2> pref(vector<T2>& a) { ll n=a.size(); vector<ll>pre(n,0); pre[0]=a[0]; for(int i=1; i<n; i++) pre[i]=pre[i-1]+a[i]; return pre; }

// **************************CODE*************************************
void srikar() {
    ll n;
    cin>>n;
    string s;
    cin>>s;
    bool flag=false;
    for(int i=0; i<n-1; i++)
    {
        if(s[i]=='R'&&s[i+1]=='L')
        {
            if(i==n-2)
            {
                flag=true;
            }
            ll l=i;
            ll j=i+1;
            ll cnt1=0;
            while(l>=0&&s[l]=='R'){
                cnt1++;
                l--;
            }
            ll cnt2=0;
            while(j<n&&s[j]=='L'){
                cnt2++;
                j++;
            }
            // cnt1++;
            // cout<<cnt1<<" "<<cnt2<<endl;
            i++;
            ll p=(cnt1+cnt2)/2;
            if((cnt1+cnt2)%2==0)
            {
                cout<<p<<" "<<p<<" ";
            }
            else
            {
                if(cnt2%2==1)
                {
                    cout<<p<<" "<<p+1<<" ";
                }
                else if(cnt1%2==1)
                {
                    cout<<p+1<<" "<<p<<" ";
                }
            }
        }
        else
        {
            cout<<0<<" ";
        }
    }
    if(!flag)
    cout<<0<<" ";
    cout<<endl;
}
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL); 
    ll t=1; 
    cin>>t; 
    while(t--) 
    srikar(); 
    return 0;
}