Cod sursa(job #2923559)

Utilizator Alex18maiAlex Enache Alex18mai Data 15 septembrie 2022 19:44:28
Problema Cautare binara Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.27 kb
//ALEX ENACHE

// < INCLUDE > ----------------------------------------------------------------

#include <bits/stdc++.h>

using namespace std;

// < PRAGMA > -----------------------------------------------------------------

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

// < PRECODED > ---------------------------------------------------------------

long long lgput(long long a, long long b, long long MOD) {
    long long ret = 1LL;
    while (b) {
        if (b & 1LL) ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1LL;
    }

    return (ret % MOD);
}

long long inv_mod(long long x, long long MOD) {
    return lgput(x, MOD - 2, MOD);
}

long long gcd(long long a, long long b) {
    long long c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long lcm(long long a, long long b) {
    if (a == 0 && b == 0) return 0;
    return a / gcd(a, b) * b;
}

long long modd(long long nr, long long MOD) {
    return ((nr % MOD) + MOD) % MOD;
}

long long big_rand() {
    return 1LL * rand() * RAND_MAX + rand();
}

long long xtime() {
    return clock() * 1000LL / CLOCKS_PER_SEC;
}

bool exist(double nr, double eps) {
    return (nr < -eps) || (nr > eps);
}

int bit_count(long long n) {
    int cont = 0;
    while (n) {
        if (n & 1) {
            cont++;
        }
        n >>= 1;
    }
    return cont;
}

// < START > ------------------------------------------------------------------

void start() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cout << setprecision(10) << fixed;
    srand(time(nullptr));
}

// < CONSTANTS > --------------------------------------------------------------

const double PI = acos(-1);
const double eps = 1e-6;
const long long inf = 1e9;
const long long MOD = 1e9 + 7;

mt19937 generator(time(nullptr));
uniform_int_distribution<int> distribution(-inf, inf);


// < STRUCTURES > -------------------------------------------------------------


// < VARIABLES > --------------------------------------------------------------

int n, k;
string s;

map < char, int > mapTo = {
        {'R', 0},
        {'S', 1},
        {'P', 2}

};
vector < int > fv;

// < FUNCTIONS > --------------------------------------------------------------

void read() {

    cin>>n>>k;
    cin>>s;

    fv.resize(3, 0);
}

string solveString(string now){
    int cont = 0;
    for (int i=0; i<3; i++){
        if (fv[i]){
            cont++;
        }
    }
    if (cont < 2)
        return now;


    string ans;
    vector < bool > ansBool(now.size(), false);

    char winner, loser;
    int winnerCont = 0;

    if (fv[0] && fv[1]){
        winner = 'R';
        loser = 'S';
    }
    if (fv[1] && fv[2]){
        winner = 'S';
        loser = 'P';
    }
    if (fv[0] && fv[2]){
        winner = 'P';
        loser = 'R';
    }

    for (int i=0; i<now.size(); i++){
        if (now[i] == winner){
            winnerCont++;
            continue;
        }
        ansBool[i - min(k, winnerCont)] = true;
    }

    for (int i=0; i<now.size(); i++){
        if (ansBool[i]){
            ans += loser;
        }
        else{
            ans += winner;
        }
    }


    return ans;
}

void solve() {
    read();

    string ans;
    string now;

    for (auto &x : s){
        int cont = 0;
        for (int i=0; i<3; i++){
            if (fv[i]){
                cont++;
            }
        }
        if (cont == 2 && fv[mapTo[x]] == 0){
            ans += solveString(now);
            now = "";
            for (int i=0; i<3; i++){
                fv[i] = 0;
            }
        }
        fv[mapTo[x]]++;
        now += x;
    }

    ans += solveString(now);

    cout<<ans<<'\n';
}

// < MAIN > -------------------------------------------------------------------

int main() {

    start();

    int t = 1;
    //cin>>t;

    for (int i=1; i<=t; i++){

        #ifdef LOCAL
            long long start = xtime();
            cerr<<"Test "<<i<<'\n';
        #endif

        solve();

        #ifdef LOCAL
            cerr<<"Time: "<<xtime()-start<<"ms"<<'\n';
            cerr<<'\n';
        #endif
    }

    return 0;
}

// < TROUBLESHOOT > -----------------------------------------------------------

/*
Pre-submit:
Write a few simple test cases, if sample is not enough.
Are time limits close? If so, generate max cases.
Is the memory usage fine?
Could anything overflow?
Make sure to submit the right file.

Wrong answer:
Print your solution! Print debug output, as well.
Are you clearing all datastructures between test cases?
Can your algorithm handle the whole range of input?
Read the full problem statement again.
Do you handle all corner cases correctly?
Have you understood the problem correctly?
Any uninitialized variables?
Any overflows?
Confusing N and M, i and j, etc.?
Are you sure your algorithm works?
What special cases have you not thought of?
Are you sure the STL functions you use work as you think?
Add some assertions, maybe resubmit.
Create some testcases to run your algorithm on.
Go through the algorithm for a simple case.
Go through this list again.
Explain your algorithm to a team mate.
Ask the team mate to look at your code.
Go for a small walk, e.g. to the toilet.
Is your output format correct? (including whitespace)
Rewrite your solution from the start or let a team mate do it.

Runtime error:
Have you tested all corner cases locally?
Any uninitialized variables?
Are you reading or writing outside the range of any vector?
Any assertions that might fail?
Any possible division by 0? (mod 0 for example)
Any possible infinite recursion?
Invalidated pointers or iterators?
Are you using too much memory?
Debug with resubmits (e.g. remapped signals, see Various).

Time limit exceeded:
Do you have any possible infinite loops?
What is the complexity of your algorithm?
Are you copying a lot of unnecessary data? (References)
How big is the input and output? (consider scanf)
Avoid vector, map. (use arrays/unordered_map)
What do your team mates think about your algorithm?

Memory limit exceeded:
What is the max amount of memory your algorithm should need?
Are you clearing all datastructures between test cases?
*/