Source Code
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair <int,int>
#define F first
#define S second
#define ever (;;)

const int N = 200100;

int n,ans;
char A[N];
string s;
set <int> rs;
set <int> :: iterator it;

int main()
{
    scanf("%s",&A);
    s = A;
    n = s.length();

    if( n == 2 )
    {
        if( s[1] == 'N' )
            printf("1\nNR\n");
        else
            printf("0\nNR\n");

        return 0;
    }

    if( s[1] == 'N' && s[2] == 'N' )
    {
        s[1] = 'R';
        ans++;
    }

    for(int i=1;i<n;i++)
    {
        if( s[i] == 'R' )
        {
            if( (int)(rs.size()) <= 1 )
            {
                rs.insert(i);
                continue;
            }

            it = rs.end();
            it--;
            int lastR = (*it);
            it--;
            int prelast = (*it);

            if( (lastR-prelast-1)*2 > i-lastR-1  )
            {
                rs.erase(lastR);
                s[lastR] = 'N';
                ans--;
            }

            rs.insert(i);
            continue;
        }

        if( (int)(rs.size()) == 1 )
        {
            it = rs.end();
            it--;
            int lastR = (*it);

            if( i - lastR >= 2 )
            {
                s[i] = 'R';
                rs.insert(i);
                ans++;
            }

            continue;
        }

        it = rs.end();
        it--;
        int lastR = (*it);
        it--;
        int prelast = (*it);

        if( (lastR-prelast-1)*2 <= i-lastR-1  )
        {
            rs.insert(i);
            s[i] = 'R';
            ans++;
        }
    }

    printf("%d\n%s\n",ans,s.c_str());
}
Copy
Never Gonna Give You Up Naseem17
GNU G++17
7 ms
1.4 MB
Accepted