QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198092#3516. Dungeon CrawlerGamal74#WA 777ms163784kbC++203.7kb2023-10-03 02:09:162023-10-03 02:09:17

Judging History

This is the latest submission verdict.

  • [2023-10-03 02:09:17]
  • Judged
  • Verdict: WA
  • Time: 777ms
  • Memory: 163784kb
  • [2023-10-03 02:09:16]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl

void Gamal() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

const int N = 1000 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;

vector<pair<int, string>> adj[N];

map<string, vector<pair<string, string>>> mp;
map<string, bool> vis;
map<string, int> id;

void dfs(string &s) {
    vis[s] = true;
    for (auto &x: mp[s]) {
        if (x.fi != "-1")continue;
        cout << 'W' << ' ' << x.se << endl;
        string nxt, m;
        cin >> nxt >> m;
        x.fi = nxt;
        if (!vis.count(nxt)) {
            for (auto c: m) {
                string a, b = "-1";
                a += c;
                if (a == x.se)b = s;
                mp[nxt].emplace_back(b, a);
            }
            dfs(nxt);
        }
        cout << 'W' << ' ' << x.se << endl;
        cin >> nxt >> m;
    }
}

bool match(string &s, int u) {
    id[s] = u;
    if (adj[u].size() != mp[s].size())return false;
    for (int i = 0; i < adj[u].size(); ++i) {
        if (adj[u][i].se != mp[s][i].se)return false;
        string nxt = mp[s][i].fi;
        int v = adj[u][i].fi;
        if (id.count(nxt)) {
            if (id[nxt] != v)return false;
        } else if (!match(nxt, v))return false;
    }
    return true;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            string c;
            cin >> c;
            int v;
            cin >> v;
            v--;
            for (auto &a: adj[i]) {
                if (a.fi == v) {
                    a.se += c;
                    v = -1;
                    break;
                }
            }
            if (~v)adj[i].emplace_back(v, c);
        }
        for (auto &a: adj[i]) {
            sort(all(a.se));
        }
        sort(all(adj[i]), [](pair<int, string> &a, pair<int, string> &b) {
            return a.se < b.se;
        });
    }
    string s;
    cin >> s;
    string nxt;
    cin >> nxt;
    for (auto c: nxt) {
        string a;
        a += c;
        mp[s].emplace_back("-1", a);
    }
    dfs(s);
    for (auto &x: mp) {
        vector<pair<string, string>> v;
        for (auto y: x.se) {
            for (auto &z: v) {
                if (z.fi == y.fi) {
                    z.se += y.se;
                    y.fi = "-1";
                    break;
                }
            }
            if (y.fi != "-1")v.emplace_back(y.fi, y.se);
        }
        for (auto &y: v)sort(all(y.se));
        sort(all(v), [](pair<string, string> &a, pair<string, string> &b) {
            return a.se < b.se;
        });
        mp[x.fi] = v;
    }
    if (mp.size() != n) {
        cout << "R no" << endl;
        return;
    }
    int cnt = 0, node = -1;
    for (int i = 0; i < n; ++i) {
        id.clear();
        if (match(s, i) && id.size() == n) {
            cnt++;
            node = i;
        }
        if (cnt > 1) {
            cout << "R ambiguous" << endl;
            return;
        }
    }
    if (cnt == 1) {
        cout << "R " << node + 1 << endl;
    } else cout << "R no" << endl;
}


signed main() {
    Gamal();
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3580kb

input:

3
2 D 2 B 3
2 P 3 D 1
2 P 2 B 1
fountain DB
obelisk DP
crystals PB
fountain BD
crystals PB
obelisk DP
fountain BD
crystals PB
fountain BD

output:

W D
W P
W B
W B
W P
W D
W B
W B
R 1

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

2
2 A 2 B 2
2 B 1 A 1
fountain BA
obelisk AB
fountain BA
obelisk AB
fountain BA
obelisk AB
fountain AB

output:

W B
W A
W A
W B
W A
W A
R ambiguous

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

4
2 A 2 B 4
2 B 3 A 1
2 A 4 B 2
2 B 1 A 3
fountain BA
cauldron AB
crystals BA
obelisk AB
fountain BA
obelisk AB
crystals AB
cauldron BA
fountain AB
obelisk AB
fountain BA

output:

W B
W A
W B
W A
W A
W B
W A
W B
W A
W A
R ambiguous

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 4744kb

input:

1000
2 A 2 B 1000
2 B 3 A 1
2 A 4 B 2
2 A 3 B 5
2 A 6 B 4
2 B 7 A 5
2 B 6 A 8
2 B 9 A 7
2 A 10 B 8
2 B 11 A 9
2 A 12 B 10
2 B 13 A 11
2 B 12 A 14
2 B 15 A 13
2 B 14 A 16
2 B 17 A 15
2 A 18 B 16
2 A 17 B 19
2 A 20 B 18
2 B 21 A 19
2 B 20 A 22
2 B 23 A 21
2 A 24 B 22
2 A 23 B 25
2 B 24 A 26
2 A 25 B 2...

output:

W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
...

result:

ok 

Test #5:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

4
2 B 4 A 2
2 A 1 B 3
2 A 4 B 2
2 A 3 B 1
fountain BA
obelisk AB
fountain BA
obelisk AB
fountain BA
obelisk AB
fountain AB

output:

W B
W A
W A
W B
W A
W A
R no

result:

ok 

Test #6:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

8
2 A 2 B 8
2 A 1 B 3
2 A 4 B 2
2 B 5 A 3
2 A 6 B 4
2 B 7 A 5
2 B 6 A 8
2 B 1 A 7
fountain BA
cauldron AB
crystals BA
obelisk AB
fountain BA
obelisk AB
crystals AB
cauldron BA
fountain AB
obelisk AB
fountain BA

output:

W B
W A
W B
W A
W A
W B
W A
W B
W A
W A
R no

result:

ok 

Test #7:

score: 0
Accepted
time: 8ms
memory: 4340kb

input:

1000
2 A 2 B 1000
2 B 3 A 1
2 B 2 A 4
2 A 3 B 5
2 A 6 B 4
2 A 5 B 7
2 A 8 B 6
2 B 9 A 7
2 B 8 A 10
2 A 9 B 11
2 A 12 B 10
2 A 11 B 13
2 A 14 B 12
2 B 15 A 13
2 A 16 B 14
2 B 17 A 15
2 B 16 A 18
2 B 19 A 17
2 A 20 B 18
2 B 21 A 19
2 B 20 A 22
2 B 23 A 21
2 A 24 B 22
2 A 23 B 25
2 A 26 B 24
2 A 25 B 2...

output:

W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
...

result:

ok 

Test #8:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

2
2 B 2 A 2
2 A 1 B 1
fountain BA
cauldron AB
crystals BA
obelisk AB
fountain BA
obelisk AB
crystals AB
cauldron BA
fountain AB
obelisk AB
fountain BA

output:

W B
W A
W B
W A
W A
W B
W A
W B
W A
W A
R no

result:

ok 

Test #9:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

4
2 B 4 A 2
2 A 1 B 3
2 A 4 B 2
2 A 3 B 1
fountain BA
holygrail AB
sword BA
weapons AB
shrine BA
cauldron AB
crystals AB
obelisk BA
fountain AB
obelisk AB
crystals BA
cauldron AB
shrine AB
weapons BA
sword AB
holygrail BA
fountain BA
obelisk AB
fountain AB

output:

W B
W A
W B
W A
W B
W A
W B
W A
W A
W B
W A
W B
W A
W B
W A
W B
W A
W A
R no

result:

ok 

Test #10:

score: 0
Accepted
time: 10ms
memory: 4324kb

input:

500
2 B 500 A 2
2 B 3 A 1
2 B 2 A 4
2 B 5 A 3
2 A 6 B 4
2 A 5 B 7
2 A 8 B 6
2 A 7 B 9
2 A 10 B 8
2 B 11 A 9
2 B 10 A 12
2 B 13 A 11
2 B 12 A 14
2 B 15 A 13
2 A 16 B 14
2 B 17 A 15
2 B 16 A 18
2 A 17 B 19
2 A 20 B 18
2 B 21 A 19
2 B 20 A 22
2 A 21 B 23
2 A 24 B 22
2 B 25 A 23
2 B 24 A 26
2 A 25 B 27
...

output:

W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
...

result:

ok 

Test #11:

score: 0
Accepted
time: 219ms
memory: 4508kb

input:

999
2 B 998 A 2
2 B 3 A 1
2 A 4 B 2
2 B 5 A 3
2 A 6 B 4
2 A 5 B 7
2 A 8 B 6
2 B 9 A 7
2 A 10 B 8
2 B 11 A 9
2 B 10 A 12
2 A 11 B 13
2 A 14 B 12
2 A 13 B 15
2 A 16 B 14
2 B 17 A 15
2 B 16 A 18
2 A 17 B 19
2 B 18 A 20
2 B 21 A 19
2 A 22 B 20
2 A 21 B 23
2 A 24 B 22
2 A 23 B 25
2 A 26 B 24
2 A 25 B 27
...

output:

W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
...

result:

ok 

Test #12:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

3
2 D 2 B 3
2 P 3 D 1
2 P 2 B 1
obelisk PD
crystals LP
fountain LD
obelisk DP
fountain LD
crystals LP
obelisk DP
fountain LD
obelisk DP

output:

W P
W L
W D
W D
W L
W P
W D
W D
R no

result:

ok 

Test #13:

score: -100
Wrong Answer
time: 777ms
memory: 163784kb

input:

8
2 A 2 B 8
2 B 3 A 1
2 A 4 B 2
2 B 5 A 3
2 A 6 B 4
2 B 7 A 5
2 A 8 B 6
2 B 1 A 7
fountain BA
aaaaacexhb AB
aaaaacexha BA
aaaaacexgz AB
aaaaacexgy BA
aaaaacexgx AB
aaaaacexgw AB
aaaaacexgv BA
aaaaacexgu AB
aaaaacexgt AB
aaaaacexgs BA
aaaaacexgr AB
aaaaacexgq AB
aaaaacexgp BA
aaaaacexgo AB
aaaaacexgn...

output:

W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
W A
W B
...

result:

wrong answer Too many moves