QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#620227 | #8046. Rock-Paper-Scissors Pyramid | mhw# | WA | 73ms | 54952kb | C++20 | 2.4kb | 2024-10-07 17:04:08 | 2024-10-07 17:04:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
using i64 = long long;
const i64 P = 998244353;
const int N = 1e6 + 6;
vector<int> g[N];
int in[N], d[N];
void solve() {
string s;
cin >> s;
int n = s.size();
for (int i = 0; i <= n; i++)
{
g[i].clear();
in[i] = d[i] = 0;
}
s = " " + s;
int lst = 1;
for (int i = 1; i <= n; i++)
{
if (s[i] == s[lst]) ;
else
{
if (s[i] == 'S') // 剪刀
{
if (s[lst] == 'P') g[lst].push_back(i);
else if (s[lst] == 'R') g[i].push_back(lst);
}
else if (s[i] == 'P') // 布
{
if (s[lst] == 'S') g[i].push_back(lst);
else if (s[lst] == 'R') g[lst].push_back(i);
}
else if (s[i] == 'R') // 石头
{
if (s[lst] == 'P') g[i].push_back(lst);
else if (s[lst] == 'S') g[lst].push_back(i);
}
lst = i;
}
}
for (int i = 1; i <= n; i++)
{
// cout << i << '\n';
for (auto j: g[i])
{
in[j]++;
// cout << j << ' ';
}
// cout << '\n';
}
queue<pii> q;
for (int i = 1; i <= n; i++)
if (in[i] == 0) q.push({i, 0});
while (q.size())
{
auto [u, w] = q.front();
d[u] = w;
q.pop();
for (auto v: g[u])
{
in[v]--;
if (in[v] == 0) q.push({v, w + 1});
}
}
int mx = 0;
string ans = "";
for (int i = 1; i <= n; i++) mx = max(mx, d[i]);
for (int i = 1; i <= n; i++)
{
if (d[i] == mx) ans += s[i];
}
auto cmp = [&](char x, char y) -> bool {
if (x == 'S' && y == 'P') return true;
else if (x == 'P' && y == 'R') return true;
else if (x == 'R' && y == 'S') return true;
return false;
};
string t = ans;
if (t.size() == 1) {
cout << t << '\n';
} else if (cmp(t[0], t[1])) {
cout << t[0] << '\n';
} else {
cout << t.back() << '\n';
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/*
1
SPRPRS
3
SPSRRPR
SPRS
SPPRSSP
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5932kb
input:
2 SPR SPSRRP
output:
S P
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 73ms
memory: 54952kb
input:
1 RPPSRPPRSRSRRRPPSPRPRSRRSRRPPPRSPSSRRRSPPPRRRPRRRSSRPSSRPRRPSRRRPRSRPSRPSRRSPPRPRRRSPRSSSRPRRRPPSRRRRPPSRSRRRPRPRPRPPRRSRRPSRPPSRRRSRRSRRSPSRPRPSPSSRRSPSPSRPRRRPPRSRSPSPPRRPRSRPPSSSRPSPRRPSSSPRRSRRSRRSRSPSSSSRSSPPRRRRPRRRSPSRSPRSSPRSPSPRPRRRPPRPPRPPPSRRRRSSPRRSRRRPRRRSSRRPSRPPRSPPSPPPSPSPSPPSSPRRR...
output:
P
result:
wrong answer 1st lines differ - expected: 'R', found: 'P'