/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 324.0 KiB
#2 Accepted 34ms 584.0 KiB
#3 Accepted 26ms 588.0 KiB
#4 Accepted 33ms 3.008 MiB
#5 Accepted 180ms 29.422 MiB
#6 Accepted 195ms 29.387 MiB

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pe(c) for (auto &e : c) cout << e << ' '; cout << '\n'
#define ps(b) cout << (b ? "YES" : "NO") << '\n'
#ifdef LOCAL
#include "def.h"
#else
#define ck(...)
#endif
const ll M = 1e9 + 7, N = 2e5 + 5;
map<tuple<int, int, bool, int, int>, bool> dp;
bool rec(int ev, int od, bool turn, int r, int h) {
    if(ev<0 or od<0) return turn;
    auto it = dp.find({ev, od, turn, r, h});
    if(it!=dp.end()) return it->second;
    bool ck;
    if(turn) {
        if(r==-1) {
            ck = (rec(ev-1, od, 0, 1, h) || rec(ev, od-1, 0, 0, h));
        }
        else if(r==0) {
            ck = rec(ev-1, od, 0, 1, h);
        }
        else ck = rec(ev, od-1, 0, 0, h);
    }
    else {
        if(h==-1) {
            ck = !(!rec(ev-1, od, 1, r, 1) or !rec(ev, od-1, 1, r, 0));
        }
        else if(h==0) {
            ck = rec(ev-1, od, 1, r, 1);
        }
        else ck = rec(ev, od-1, 1, r, 0);
    }
    return dp[{ev, od, turn, r, h}] = ck;
}

void test(int tc) {
    ll n = 0, m = 0, a = 0, b = 0, c = 0, d = 0, i = 0, j = 0, k = 0, q = 0;
    cin >> n;
    for (i = 0; i < n; ++i) { cin >> a; if(a&1) d++; else c++; }
    bool ck = rec(c, d, 1, -1, -1);
    cout << (ck ? "Roy" : "Hridoy") << '\n';
    dp.clear();
    // cout << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit | cin.badbit);
    int tc = 0, t = 1;
    cin >> t;
    while (tc < t) test(++tc);
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1102 Odd-Even Game
Contest
Brain Booster #6
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-03 16:55:30
Judged At
2024-11-11 02:47:18
Judged By
Score
100
Total Time
195ms
Peak Memory
29.422 MiB