結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー Ian
提出日時 2026-04-19 16:55:55
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 117 ms / 2,000 ms
コード長 2,638 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,419 ms
コンパイル使用メモリ 343,116 KB
実行使用メモリ 36,348 KB
最終ジャッジ日時 2026-04-19 16:56:22
合計ジャッジ時間 8,159 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const u64 CAP = (u64)2e18 + 5;

u64 smul(u64 a, u64 b){ if(!a||!b) return 0; if(a > CAP/b) return CAP; u64 r=a*b; return r>CAP?CAP:r; }
u64 sadd(u64 a, u64 b){ u64 s=a+b; if(s>CAP||s<a) return CAP; return s; }

int W_[3][3];
struct BIT{ int n; vector<int> t;
  void init(int n_){n=n_; t.assign(n+2,0);}
  void upd(int i,int v){for(;i<=n;i+=i&-i) t[i]+=v;}
  int kth(int k){int p=0; for(int i=17;i>=0;i--){int q=p+(1<<i); if(q<=n&&t[q]<k){p=q;k-=t[q];}} return p+1;}
};

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  for(int i=0;i<3;i++) for(int j=0;j<3;j++) W_[i][j]=-1;
  W_[0][1]=W_[1][0]=0; W_[0][2]=W_[2][0]=2; W_[1][2]=W_[2][1]=1;
  int T; cin>>T;
  while(T--){
    int N; u64 K; cin>>N>>K;
    vector<int> A(N-1); for(auto&x:A) cin>>x;
    int tot=2*N;
    vector<int> LC(tot,-1), RC(tot,-1);
    vector<array<u64,3>> cnt(tot);
    for(int i=0;i<N;i++) cnt[i]={1,1,1};
    int num=N;
    BIT bit; bit.init(N);
    for(int i=1;i<=N;i++) bit.upd(i,1);
    vector<int> na(N+2);
    for(int i=1;i<=N;i++) na[i]=i-1;
    for(int i=0;i<N-1;i++){
      int p1=bit.kth(A[i]), p2=bit.kth(A[i]+1);
      int id=num++; LC[id]=na[p1]; RC[id]=na[p2];
      auto&cl=cnt[LC[id]]; auto&cr=cnt[RC[id]];
      cnt[id][0]=sadd(smul(cl[0],cr[1]),smul(cl[1],cr[0]));
      cnt[id][1]=sadd(smul(cl[1],cr[2]),smul(cl[2],cr[1]));
      cnt[id][2]=sadd(smul(cl[0],cr[2]),smul(cl[2],cr[0]));
      na[p1]=id; bit.upd(p2,-1);
    }
    int root=na[bit.kth(1)];
    struct F{ int v,ph,lv; array<u64,3> w; };
    int tg[3]={1,0,2}; const char* ch="PRS";
    for(int ti=0;ti<3;ti++){
      int t=tg[ti];
      if(cnt[root][t]<K){ cout<<-1<<"\n"; continue; }
      u64 Kc=K; string ans; vector<F> st;
      array<u64,3> w0={0,0,0}; w0[t]=1;
      st.push_back({root,0,0,w0}); int rv=-1;
      while(!st.empty()){
        F&f=st.back();
        if(LC[f.v]==-1){
          for(int c=0;c<3;c++){ if(Kc<=f.w[c]){ans.push_back(ch[c]); rv=c; break;} Kc-=f.w[c]; }
          st.pop_back(); continue;
        }
        if(f.ph==0){
          array<u64,3> wL={0,0,0}; auto&cr=cnt[RC[f.v]];
          for(int l=0;l<3;l++) for(int r=0;r<3;r++) if(l!=r){ int v=W_[l][r]; wL[l]=sadd(wL[l],smul(cr[r],f.w[v])); }
          int ch2=LC[f.v]; f.ph=1; st.push_back({ch2,0,0,wL});
        } else if(f.ph==1){
          f.lv=rv; array<u64,3> wR={0,0,0};
          for(int r=0;r<3;r++) if(r!=f.lv){ int v=W_[f.lv][r]; wR[r]=f.w[v]; }
          int ch2=RC[f.v]; f.ph=2; st.push_back({ch2,0,0,wR});
        } else { rv=W_[f.lv][rv]; st.pop_back(); }
      }
      cout<<ans<<"\n";
    }
  }
}
0