Source Code
/*
    # Enjoy the journey #
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define forq(i , a , b) for (int i = (a); i <= (b); ++i)
#define qrof(i , b , a) for (int i = (a); i >= (b); --i)
#define forr(i , b) forq( i , 0 , b - 1 )
#define F first
#define S second
#define IF ->first
#define IS ->second
#define endl '\n'
#define qqmemset(array , val) memset (array , val , sizeof(array))
#define ALLV(vect) vect.begin() , vect.end()
#define mid (st + en) / 2
#define mid1 (2 * st + en) / 3
#define mid2 (2 * en + st) / 3
#define lef 2 * Node
#define rig lef + 1
mt19937 rng( chrono::steady_clock::now().time_since_epoch().count() );
#define Ran(a, b) rng() % ( (b) - (a) + 1 ) + (a)

ll R = 7 + 1e9 , R1 = 19491001 , R2 = 236 , NUMTESTCASE ;
const ll NN = 10 + 1e6 ;
const double pi = acos(-1.0) ;
int di [8] = {1 , 0 , -1 , 0  , 1 , -1 , 1  , -1 } , dj [8] = {0 , 1 , 0  , -1 , 1 , -1 , -1 , 1  } ;
string s ;
int n , G [NN] ;

int Solve (int x , int d) {
    if (x == 0) return 0 ;

    int NLen = G [x] - x - 1 ;
    int p = x + 2 * d + 1 ;
    if (p > n) return 0 ;
    if (NLen - 2 * d - 1 >= 0 || G [x] == 0) {
        s [p] = 'R' ;
        G [p] = G [x] ;
        return 1 + Solve(p , 2 * d) ;
    }
    return Solve(G [x] , G [x] - x - 1) ;
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL) ;
    cin >> s ;
    n = s.size () ;
    s = "#" + s ;
    string TT = s ;
    int i = 1 , Ans = 0 ;
    while (i <= n && s [i] == 'N') i ++ ;
    if (i > n) i = 2 , s [i] = 'R' , Ans ++ ;
    int j = i + 1 ;
    while (j <= n && s [j] == 'N') j ++ ;
    if (j > n && i + 2 <= n) j = i + 2 , s [j] = 'R' , Ans ++ ;
    int Last = -1;
    forq (i , 1 , n) {
        if (s [i] == 'N') continue ;;
        if (Last == -1) {
            Last = i ;
            continue ;
        }
        G [Last] = i ;
        Last = i ;
    }
    pair <int, string > Temp = {Ans + Solve(j , j - i - 1) , "" } ;

    forq (i , 1 , n)
        Temp.S += s [i] ;

    if (n < 4) {
        cout << Temp.F << "\n" << Temp.S ;
        return 0 ;
    }
    s = TT ;
    Ans = (s [4] != 'R');

    s [4] = 'R' ;
    Ans += Solve(4 , 1) ;
    auto Check = [&] () {
        qqmemset(G , 0) ;
        int Last = -1 ;
        forq (i , 1 , n){
            if (s [i] == 'N') continue ;
            if (Last == -1) {
                Last = i ;
                continue;
            }
            G [Last] = i ;
            Last = i ;
        }
        int OldD = 1 , Curr = 4 ;
        while (Curr <= n) {
            if (G [Curr] == 0) return true ;
            int Next = G [Curr] - Curr - 1 ;
            if (Next < 2 * OldD) return false ;
            OldD = Next ;
            Curr = G [Curr] ;
        }
        return true ;
    };
    if (Check ()) {
        if (Temp.F < Ans) {
            Temp .F = Ans ;
            Temp.S = "" ;
            forq (i , 1 , n)
                Temp.S += s [i] ;
        }
    }
    cout << Temp.F << endl << Temp.S ;
    return 0;
}
Copy
Never Gonna Give You Up Practice_Til_Red00
GNU G++17
9 ms
5.7 MB
Wrong Answer