[text] Rock-paper-scissor

Viewer

copydownloadembedprintName: Rock-paper-scissor
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. // policy based datastructure
  5. // #include <ext/pb_ds/assoc_container.hpp>
  6. // using namespace __gnu_pbds;
  7. // typedef tree<int,null_type,less<int>,rb_tree_tag,
  8. // tree_order_statistics_node_update> indexed_set;
  9.  
  10. #define ll long long
  11. #define en '\n'
  12. #define ff first
  13. #define ss second
  14. #define pb push_back
  15. #define MP make_pair
  16. // #define mod 1000000007
  17. #define mod 998244353
  18. #define fast                      \
  19.     ios_base::sync_with_stdio(0); \
  20.     cin.tie(0);                   \
  21.     cout.tie(0);
  22. using namespace std;
  23.  
  24. typedef vector<ll> vi;
  25. typedef vector<vi> vvi;
  26. typedef priority_queue<ll>pqi;
  27. typedef priority_queue<ll,vi,greater<ll>> minpqi;
  28. typedef pair<ll, ll> pii;
  29.  
  30. #define all(x) x.begin(), x.end()
  31. #define present(c, key) (find(all(c), key) != c.end())
  32. #define tr(c, it) for (auto it : c)
  33. #define fr(i, s, e) for (ll i = s; i < e; i++)
  34. #define revfr(i, s, e) for (ll i = s - 1; i >= e; i--)
  35. #define getv(v, n)             \
  36.     for (ll i = 0; i < n; i++) \
  37.         cin >> v[i];
  38.  
  39. template <typename T>
  40. ostream &operator<<(ostream &os, vector<T> &v)
  41. {
  42.  
  43.     for (auto element : v)
  44.     {
  45.         os << element << ' ';
  46.     }
  47.     return os;
  48. }
  49. inline void add(ll &a, ll b)
  50. {
  51.     a += b;
  52.     if (a >= mod)
  53.         a -= mod;
  54. }
  55.  
  56. inline void sub(ll &a, ll b)
  57. {
  58.     a -= b;
  59.     if (a < 0)
  60.         a += mod;
  61. }
  62.  
  63. inline ll mul(ll a, ll b, ll p = mod)
  64. {
  65.     return (ll)((long long)a * b % p);
  66. }
  67.  
  68. inline ll power(ll a, long long b, ll p = mod)
  69. {
  70.     ll res = 1;
  71.     while (b > 0)
  72.     {
  73.         if (b & 1)
  74.         {
  75.             res = mul(res, a, p);
  76.         }
  77.         a = mul(a, a, p);
  78.         b >>= 1;
  79.     }
  80.     return res;
  81. }
  82. inline ll inv(ll a, ll p = mod)
  83. {
  84.     a %= p;
  85.     if (a < 0)
  86.         a += p;
  87.     ll b = p, u = 0, v = 1;
  88.     while (a)
  89.     {
  90.         ll t = b / a;
  91.         b -= t * a;
  92.         swap(a, b);
  93.         u -= t * v;
  94.         swap(u, v);
  95.     }
  96.     if (u < 0)
  97.         u += p;
  98.     return u;
  99. }
  100. // inline ll lsb(ll x)
  101. // {
  102. //     return x&(~(x-1));
  103. // }
  104. // ll modexp2(ll a, ll b, ll c, ll p) // calculate (a^(b^c))%prime
  105. // {
  106. //     // By Fermat's Little Theorem (a^(p-1))%p = 1 if p is prime 
  107. //     ll x = power(b,c,p-1);  // so we first find remainder when b^c is divided by p-1
  108. //     return (power(a,x,p));  // then just do (a^remainder)%p
  109.  
  110. // }
  111. ll gcd(ll a, ll b)
  112. {
  113.     if (a == 0 or b == 0)
  114.         return a ^ b;
  115.     return gcd(b, a % b);
  116. }
  117. ll n;
  118. ll win(ll x,ll y)
  119. {
  120.     return (((x+1)%3)==y);
  121. }
  122. ll a[1010];
  123. ll dp[1010][3][1010];
  124. pii back[1010][3][1010];
  125. ll rec(ll lvl,ll last,ll k_left)
  126. {
  127.     if(k_left<0)return -1e18;
  128.     if(lvl==n)return 0;
  129.     if(dp[lvl][last][k_left]!=-1)return dp[lvl][last][k_left];
  130.     ll ans=-1;
  131.     ll l=0,m=0,o=0;
  132.     fr(i,0,3)
  133.     {
  134.         ll x=win(i,a[lvl])+rec(lvl+1,i,k_left-1+(i==last));
  135.         // cout<<"x="<<x<<" i="<<i<<en;
  136.         if(ans<x)
  137.         {
  138.             ans=x;
  139.             back[lvl][last][k_left]={i,k_left-1+(i==last)};
  140.         }
  141.         if(i==0)l=x;
  142.         else if(i==1)m=x;
  143.         else o=x;
  144.     }
  145.     // cout<<"lvl="<<lvl<<" last="<<last<<" k_left="<<k_left<<en;
  146.     // cout<<"l="<<l<<" m="<<m<<" o="<<o<<en;
  147.     // cout<<"ans="<<ans<<" back="<<back[lvl][last][k_left].ff<<" "<<back[lvl][last][k_left].ss<<en<<en;
  148.     return dp[lvl][last][k_left]=ans;
  149. }
  150. void solve()
  151. {
  152.     ll k;
  153.     cin>>n>>k;
  154.     string s;
  155.     cin>>s;
  156.     map<char,ll>mp;
  157.     mp['P']=0;
  158.     mp['R']=1;
  159.     mp['S']=2;
  160.     fr(i,0,n)
  161.     {
  162.         a[i]=mp[s[i]];
  163.     }
  164.     fr(i,0,n+1)fr(j,0,3)fr(l,0,k+1)dp[i][j][l]=-1,back[i][j][l]={-1,-1};
  165.     string ans_s="";
  166.     ll ans=-1;
  167.     pii st;
  168.     fr(i,0,3)
  169.     {
  170.         ll x=rec(0,i,k);
  171.         if(ans<x)
  172.         {
  173.             ans=x;
  174.             st={i,k};
  175.         }
  176.         // cout<<"x="<<x<<" i="<<i<<en;
  177.     }
  178.     cout<<ans<<en;
  179.     map<int,char>rmp;
  180.     rmp[0]='P';
  181.     rmp[1]='R';
  182.     rmp[2]='S';
  183.     fr(i,0,n)
  184.     {
  185.         // cout<<"i="<<i<<" st="<<st.ff<<" "<<st.ss<<en;
  186.         // cout<<rmp[st.ff]<<en;
  187.         st=back[i][st.ff][st.ss];
  188.         ans_s+=rmp[st.ff];
  189.     }
  190.     cout<<ans_s<<en;
  191.     // cout<<en<<en<<en;
  192. }
  193. using namespace std;
  194.  
  195. int main()
  196. {
  197.     fast
  198.         // #ifdef ONLINE_JUDGE
  199.         freopen("./input.txt", "r", stdin);
  200.     freopen("./output.txt", "w", stdout);
  201.     // #endif
  202.     ll _t = 1;
  203.     cin >> _t;
  204.     fr(i, 1, _t + 1)
  205.     {
  206.         // cout<<"Case #"<<i<<": ";
  207.         solve();
  208.     }
  209.     return 0;
  210. }

Editor

You can edit this paste and save as new:


File Description
  • Rock-paper-scissor
  • Paste Code
  • 07 Dec-2022
  • 4.46 Kb
You can Share it: