結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 askr58
|
| 提出日時 | 2026-04-18 19:33:14 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 2,989 bytes |
| 記録 | |
| コンパイル時間 | 3,279 ms |
| コンパイル使用メモリ | 367,724 KB |
| 実行使用メモリ | 40,144 KB |
| 最終ジャッジ日時 | 2026-04-18 19:33:28 |
| 合計ジャッジ時間 | 7,878 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 5 WA * 23 |
コンパイルメッセージ
In lambda function,
inlined from 'naive(int, ll, std::vector<int>)::<lambda(auto:65, int, std::vector<int>)> [with auto:65 = naive(int, ll, std::vector<int>)::<lambda(auto:65, int, std::vector<int>)>]' at main.cpp:105:15:
main.cpp:98:38: warning: 'i' may be used uninitialized [-Wmaybe-uninitialized]
98 | for(int i=a[i]+1;i+1<s.size();i++)swap(s[i],s[i+1]);
| ^
main.cpp: In lambda function:
main.cpp:98:33: note: 'i' was declared here
98 | for(int i=a[i]+1;i+1<s.size();i++)swap(s[i],s[i+1]);
| ^
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include <atcoder/dsu>
#include <atcoder/segtree>
int op(int x,int y){
return x+y;
}
int e(){
return 0;
}
array<string,3> solve(int n,ll k,vector<int> a){
k--;
if(n<61&&(1ll<<(n-1))<=k)return{"-1","-1","-1"};
vector<array<int,2>> graph(2*n-1,{-1,-1});
{
atcoder::dsu uf(2*n-1);
atcoder::segtree<int,op,e> seg(n);
for(int i=0;i<n;i++)seg.set(i,1);
vector<int> p(2*n-1);
iota(p.begin(),p.end(),0);
for(int i=0;i<n-1;i++){
auto f=[&](int x)->int{
return x<=a[i];
};
int l=seg.max_right<decltype(f)>(0,f);
a[i]++;
int r=seg.max_right<decltype(f)>(0,f);
//cout<<l<<" "<<r<<endl;
int pl=uf.leader(l+n-1),pr=uf.leader(r+n-1);
graph[n-2-i][0]=p[pl];
graph[n-2-i][1]=p[pr];
uf.merge(pl,pr);
uf.merge(pl,n-2-i);
p[uf.leader(pl)]=n-2-i;
seg.set(r,0);
}
}
ll cur=k;
int cnt=n-1;
auto rec=[&](auto rec,int v,array<ll,3> arr,string& ans)->int{
if(v>=n-1){
if(cnt>=61){
ans.push_back('P');
return 0;
}
ll mcur=cur>>cnt;
if(mcur>=arr[0]+arr[1]){
cur-=(arr[0]+arr[1])<<cnt;
ans.push_back('S');
return 2;
}else if(mcur>=arr[0]){
cur-=arr[0]<<cnt;
ans.push_back('R');
return 1;
}else{
ans.push_back('P');
return 0;
}
}
array<ll,3> narr;
cnt--;
narr[0]=min(k+1,arr[0]+arr[2]);
narr[1]=min(k+1,arr[1]+arr[0]);
narr[2]=min(k+1,arr[2]+arr[1]);
int c=rec(rec,graph[v][0],narr,ans);
if(c==0){
narr={0,arr[0],arr[2]};
}else if(c==1){
narr={arr[0],0,arr[1]};
}else{
narr={arr[2],arr[1],0};
}
int d=rec(rec,graph[v][1],narr,ans);
return (4-c-d)%3;
};
array<string,3> res{"","",""};
rec(rec,0,{0,1,0},res[0]);
cur=k;cnt=n-1;
rec(rec,0,{1,0,0},res[1]);
cur=k;cnt=n-1;
rec(rec,0,{0,0,1},res[2]);
return res;
}
array<string,3> naive(int n,ll k,vector<int> a){
vector<vector<string>> res(3);
auto tostring=[n](vector<int> s)->string{
string res;
for(int i=0;i<n;i++)res.push_back("PRS"[s[i]]);
return res;
};
auto judge=[n,a](vector<int> s)->int{
for(int i=0;i<n-1;i++){
if(s[a[i]]==s[a[i]+1])return -1;
int w=(4-s[a[i]]-s[a[i]+1])%3;
if(s[a[i]]!=w)swap(s[a[i]],s[a[i]+1]);
for(int i=a[i]+1;i+1<s.size();i++)swap(s[i],s[i+1]);
s.pop_back();
}
return s[0];
};
auto rec=[&](auto rec,int d,vector<int> s)->void{
if(d==n){
int r=judge(s);
if(r!=-1)res[r].push_back(tostring(s));
return;
}
for(int i=0;i<3;i++){
s.push_back(i);
rec(rec,d+1,s);
s.pop_back();
}
return;
};
rec(rec,0,{});
array<string,3> ans;
for(int i=0;i<3;i++){
ranges::sort(res[i]);
if(res[i].size()<k)ans[i]="-1";
else ans[i]=res[i][k-1];
}
swap(ans[0],ans[1]);
return ans;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int ttt;
cin>>ttt;
while(ttt--){
int n;
ll k;
cin>>n>>k;
vector<int> a(n-1);
for(int i=0;i<n-1;i++)cin>>a[i],a[i]--;
auto[s1,s2,s3]=solve(n,k,a);
cout<<s1<<"\n"<<s2<<"\n"<<s3<<endl;
}
}