結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 ponjuice
|
| 提出日時 | 2026-04-18 23:28:23 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,276 bytes |
| 記録 | |
| コンパイル時間 | 3,599 ms |
| コンパイル使用メモリ | 363,588 KB |
| 実行使用メモリ | 18,768 KB |
| 最終ジャッジ日時 | 2026-04-18 23:28:34 |
| 合計ジャッジ時間 | 9,804 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 |
| other | WA * 28 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//高速化
struct ponjuice{ponjuice(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);}}PonJuice;
//#define endl '\n' //インタラクティブ問題の時は消す
//型
using ll = long long;
using ld = long double;
template<class T>using vc = vector<T>; template<class T>using vvc = vc<vc<T>>; template<class T>using vvvc = vvc<vc<T>>;
using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>;
using vl = vc<ll>; using vvl = vvc<ll>; using vvvl = vvvc<ll>;
using pi = pair<int, int>; using pl = pair<ll, ll>;
using ull = unsigned ll;
template<class T>using priq = priority_queue<T>;
template<class T>using priqg = priority_queue<T, vc<T>, greater<T>>;
// for文
#define overload4(a, b, c, d, e, ...) e
#define rep1(n) for(ll i = 0; i < n; i++)
#define rep2(i, n) for(ll i = 0; i < n; i++)
#define rep3(i, a, b) for(ll i = a; i < b; i++)
#define rep4(i, a, b, step) for(ll i = a; i < b; i+= step)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(n) for(ll i = n-1; i >= 0; i--)
#define per2(i, n) for(ll i = n-1; i >= 0; i--)
#define per3(i, a, b) for(ll i = b-1; i >= a; i--)
#define per4(i, a, b, step) for(ll i = b-1; i >= a; i-= step)
#define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)
//関数
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define si(x) (ll)(x).size()
template<class S, class T>inline bool chmax(S& a, T b){return a < b && ( a = b , true);}
template<class S, class T>inline bool chmin(S& a, T b){return a > b && ( a = b , true);}
inline void yes(){cout << "Yes\n";}
inline void no(){cout << "No\n";}
inline void yesno(bool y = true){if(y)yes();else no();}
//定数
constexpr ll mod = 998244353;
constexpr ll minf=-(1<<29);
constexpr ll inf=(1<<29);
constexpr ll MINF=-(1LL<<60);
constexpr ll INF=(1LL<<60);
const int dx[4] ={-1, 0, 1, 0};
const int dy[4] ={ 0, 1, 0,-1};
const int dx8[8] ={-1,-1,-1, 0, 1, 1, 1, 0};
const int dy8[8] ={-1, 0, 1, 1, 1, 0,-1,-1};
string solve(const ll n,const ll k, vector<ll> a);
ll powll(ll x, ll n) {
ll res = 1;
while(n > 0) {
if(n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}
int battle(string s, const vector<ll>& a) {
map<char,int> mp;
mp['P'] = 0;
mp['R'] = 1;
mp['S'] = 2;
vector<int> now;
rep(i,0,s.size()) now.push_back(mp[s[i]]);
int n = now.size();
rep(i,0,n-1) {
vector<int> nx;
rep(j,0,now.size()) {
if(a[i]-1 == j) {
if(now[j] == now[j+1]) return -1;
if((now[j]+1)%3 == now[j+1]) nx.push_back(now[j]);
else nx.push_back(now[j+1]);
j++;
}
else {
nx.push_back(now[j]);
}
}
now.swap(nx);
}
return now[0];
}
string greedy(ll n, ll k, vector<ll> a) {
string s(n, '?');
vector<vector<string>> ans(3);
rep(i,0,powll(3,n)) {
int I = i;
rep(j,0,n) {
s[j] = "PRS"[I%3];
I /= 3;
}
int win = battle(s, a);
if(win != -1) ans[win].push_back(s);
}
if(k >= ans[0].size()) {
return "-1\n-1\n-1\n";
}
sort(all(ans[0]));
sort(all(ans[1]));
sort(all(ans[2]));
return ans[1][k] + "\n" + ans[0][k] + "\n" + ans[2][k] + "\n";
}
void test() {
int itr = 0;
while(true){
cout << (itr++) << endl;
ll n = 10, k = rand() % 16;
vector<ll> a(n-1);
rep(i,0,n-1) a[i] = rand() % (n-i-1) + 1;
if(greedy(n,k,a) != solve(n,k,a)) {
cout << n << " " << k << endl;
for(auto c: a) cout << c << " "; cout << endl;
cout << greedy(n,k,a) + "\n" + solve(n,k,a) << endl;
return;
}
// cout << greedy(n,k,a) + "\n" + solve(n,k,a) << endl;
// break;
}
}
int main() {
// test();
// return 0;
int t = 1;
cin >>t;
while(t--){
ll n,k;
cin >> n >> k;k--;
vector<ll> a(n-1);
rep(i,0,n-1) cin >> a[i];
cout << solve(n,k,a);
}
}
/*
せっかくなので、PPC は全てコメント書きます
辞書順でK番目系のやつ苦手
木DP 的な感じかな？
とりあえず木DPだと思って解いてみます
REだけになってくれて一安心
*/
#include<atcoder/segtree>
using namespace atcoder;
int add(int a, int b) {return a + b;}
int zero() {return 0;}
ll sani(ll a, ll b) {
if(INF/a <= b) return INF;
return a * b;
}
string solve(const ll n,const ll k, vector<ll> a){
// 木の構築
segtree<int,add,zero> seg(n);
rep(i,0,n) seg.set(i,1);
vector<int> node(n);
rep(i,0,n) node[i] = i;
vector<ll> l(n*2, -1);
vector<ll> r(n*2, -1);
vector<ll> cnt(n*2, 1);
rep(i,0,n-1) {
int L = seg.max_right(0, [&](int x){return x < a[i];});
int R = seg.max_right(0, [&](int x){return x < a[i]+1;});
seg.set(R, 0);
l[n+i] = node[L];
r[n+i] = node[R];
cnt[n+i] = cnt[node[L]] + cnt[node[R]];
chmin(cnt[n+i], 61);
node[L] = n+i;
}
return "";
using S = array<ll,3>; // P R S
auto sol = [&](S st) -> string {
string ans(n, '?');
bool possible = true;
auto dfs = [&](auto&&self, int nw, S p, ll K) -> pair<int,ll> {
// cout << nw << " " << K << " p:[" << p[0] << "," << p[1] << "," << p[2] << "]" << endl;
if(nw < n) {
if(K < p[0]) {
ans[nw] = 'P';
return {0, 0};
}
K -= p[0];
if(K < p[1]) {
ans[nw] = 'R';
return {1, p[0]};
}
K -= p[1];
if(K < p[2]) {
ans[nw] = 'S';
return {2, p[0]+p[1]};
}
possible = false;
return {0, 0};
}
ll lk = K / (1LL << min(60LL, cnt[r[nw]]-1));
S lp = p;
rep(i,0,3) {
lp[(i+1)% 3] += p[i];
chmin(lp[(i+1)% 3], k+1);
}
auto [lc, mc] = self(self, l[nw], lp, lk);
mc *= (1LL << min(60LL, cnt[r[nw]]-1));
// cout << nw << " " << "PRS"[lc] << " " << mc << endl;
K -= mc;
S rp = {0, 0, 0};
rp[(lc+1)%3] = p[lc%3];
rp[(lc+2)%3] = p[(lc+2)%3];
ll rk = K % sani((1LL << min(60LL, cnt[r[nw]]-1)), lp[lc]); // これ % じゃないかも
auto [rc, mc2]= self(self, r[nw], rp, rk);
// cout << nw << " " << "PRS"[rc] << " " << mc << endl;
mc += mc2;
if((lc+1)%3 == rc) return {lc, mc};
return {rc, mc};
};
dfs(dfs, n*2-2, st, k);
// cout << endl;
if(possible) return ans;
else return "-1";
};
string ans1 = sol({0, 1, 0});
string ans2 = sol({1, 0, 0});
string ans3 = sol({0, 0, 1});
return ans1 + "\n" + ans2 + "\n" + ans3 + "\n";
}
/*
RPRSP
PPSSR
PPRSP
*/