結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 Ryan Shaw
|
| 提出日時 | 2026-04-17 23:44:50 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 463 ms / 2,000 ms |
| コード長 | 5,333 bytes |
| 記録 | |
| コンパイル時間 | 3,264 ms |
| コンパイル使用メモリ | 274,016 KB |
| 実行使用メモリ | 93,404 KB |
| 最終ジャッジ日時 | 2026-04-17 23:45:17 |
| 合計ジャッジ時間 | 18,681 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
コンパイルメッセージ
main.cpp: In function 'void initcatalan(long long int)':
main.cpp:85:59: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
85 | for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
| ~~~~~~~~^
main.cpp:85:24: note: within this loop
85 | for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
| ~^~~~~~~~~~~
ソースコード
#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
const int MOD = 998244353;//
const int FACTMAX = 2000005;//
const int CATALANMAX = 1000005;//
int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX];
int expo(int a, int b){
int res=1;
a%=MOD;
while (b){
if (b&1)res=(res*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return res;
}
int inv(int num){
return expo(num, MOD-2);
}
void initfact(){
fact[0]=1;
for (int i=1; i<FACTMAX; ++i)fact[i]=(fact[i-1]*i)%MOD;
invfact[FACTMAX-1]=inv(fact[FACTMAX-1]);
for (int i=FACTMAX-2; i>=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD;
}
int ncr(int n, int r){
if (n<r||r<0)return 0;
return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD;
}
int gcd(int a, int b){
while (b){
int t=a%b;
a=b;
b=t;
}
return a;
}
int lcm(int a, int b){
int temp=gcd(a, b);
a/=temp;
b/=temp;
return a*b*temp;
}
void initcatalan(int k){
cat[0]=1;
for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
}
int add_cap(int a, int b){
if (a>=LLONG_MAX/2-b)return LLONG_MAX/2;
return a+b;
}
int mul_cap(int a, int b){
__int128 x=(__int128)a*b;
if (x>LLONG_MAX/2)return LLONG_MAX/2;
return (int)x;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct item{
int prior,value,cnt;
item *l,*r;
item(int value):prior((int)rng()),value(value),cnt(1),l(nullptr),r(nullptr){}
};
typedef item* pitem;
int cnt(pitem t){
return t?t->cnt:0;
}
void upd_cnt(pitem t){
if (t)t->cnt=1+cnt(t->l)+cnt(t->r);
}
void split(pitem t,pitem &l,pitem &r,int key,int add=0){
if (!t){
l=r=nullptr;
return;
}
int cur_key=add+cnt(t->l);
if (key<=cur_key){
split(t->l,l,t->l,key,add);
r=t;
}
else{
split(t->r,t->r,r,key,add+1+cnt(t->l));
l=t;
}
upd_cnt(t);
}
void merge(pitem &t,pitem l,pitem r){
if (!l||!r)t=l?l:r;
else if (l->prior>r->prior)merge(l->r,l->r,r),t=l;
else merge(r->l,l,r->l),t=r;
upd_cnt(t);
}
struct state{
int u,phase,left_color,k;
int w[3],left_w[3],right_w[3][3];
};
vector<int> pw;
vector<int> a,lch,rch,sz;
int n,kth,root_id;
int win[3][3]={{-1,0,2},{0,-1,1},{2,1,-1}};
char cc[3]={'P','R','S'};
int count_all(int u,int w0,int w1,int w2){
int s=add_cap(w0,add_cap(w1,w2));
return mul_cap(s,pw[sz[u]-1]);
}
string build(int target){
string ans;
ans.reserve(n);
vector<state> st;
state first;
first.u=root_id;
first.phase=0;
first.left_color=0;
first.k=kth;
for (int i=0;i<3;++i){
first.w[i]=0;
first.left_w[i]=0;
for (int j=0;j<3;++j)first.right_w[i][j]=0;
}
first.w[target]=1;
st.pb(first);
int ret_color=-1,ret_rank=0;
while (!st.empty()){
state &cur=st.back();
if (cur.u<=n){
int pref=0;
for (int c=0;c<3;++c){
if (cur.k<=pref+cur.w[c]){
ans.pb(cc[c]);
ret_color=c;
ret_rank=cur.k-pref;
break;
}
pref+=cur.w[c];
}
st.pop_back();
continue;
}
if (cur.phase==0){
int left=lch[cur.u],right=rch[cur.u];
for (int x=0;x<3;++x){
for (int y=0;y<3;++y)cur.right_w[x][y]=0;
for (int y=0;y<3;++y){
if (x==y)continue;
cur.right_w[x][y]=cur.w[win[x][y]];
}
cur.left_w[x]=count_all(right,cur.right_w[x][0],cur.right_w[x][1],cur.right_w[x][2]);
}
cur.phase=1;
state nxt;
nxt.u=left;
nxt.phase=0;
nxt.left_color=0;
nxt.k=cur.k;
for (int i=0;i<3;++i){
nxt.w[i]=cur.left_w[i];
nxt.left_w[i]=0;
for (int j=0;j<3;++j)nxt.right_w[i][j]=0;
}
st.pb(nxt);
}
else if (cur.phase==1){
cur.left_color=ret_color;
cur.phase=2;
state nxt;
nxt.u=rch[cur.u];
nxt.phase=0;
nxt.left_color=0;
nxt.k=ret_rank;
for (int i=0;i<3;++i){
nxt.w[i]=cur.right_w[cur.left_color][i];
nxt.left_w[i]=0;
for (int j=0;j<3;++j)nxt.right_w[i][j]=0;
}
st.pb(nxt);
}
else{
ret_color=win[cur.left_color][ret_color];
st.pop_back();
}
}
return ans;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
pw.assign(200005,0);
pw[0]=1;
for (int i=1;i<200005;++i)pw[i]=min(LLONG_MAX/2,mul_cap(pw[i-1],2));
while (t--){
cin>>n>>kth;
a.assign(n+1,0);
for (int i=1;i<=n-1;++i)cin>>a[i];
lch.assign(2*n+5,0);
rch.assign(2*n+5,0);
sz.assign(2*n+5,1);
pitem root=nullptr;
for (int i=1;i<=n;++i){
pitem cur=new item(i);
merge(root,root,cur);
}
int tot=n;
for (int i=1;i<=n-1;++i){
pitem t1,t2,t3,t4;
split(root,t1,t2,a[i]-1);
split(t2,t2,t3,1);
split(t3,t3,t4,1);
int x=t2->value;
int y=t3->value;
++tot;
lch[tot]=x;
rch[tot]=y;
sz[tot]=sz[x]+sz[y];
pitem cur=new item(tot);
pitem tmp;
merge(tmp,t1,cur);
merge(root,tmp,t4);
}
root_id=tot;
if (kth>pw[n-1]){
cout<<"-1\n-1\n-1\n";
continue;
}
cout<<build(1)<<"\n";
cout<<build(0)<<"\n";
cout<<build(2)<<"\n";
}
}