QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620227#8046. Rock-Paper-Scissors Pyramidmhw#WA 73ms54952kbC++202.4kb2024-10-07 17:04:082024-10-07 17:04:20

Judging History

你现在查看的是最新测评结果

  • [2024-10-07 17:04:20]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:54952kb
  • [2024-10-07 17:04:08]
  • 提交

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'