QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198090#3516. Dungeon CrawlerGamal74#WA 809ms163792kbC++203.6kb2023-10-03 02:06:052023-10-03 02:06:05

Judging History

This is the latest submission verdict.

  • [2023-10-03 02:06:05]
  • Judged
  • Verdict: WA
  • Time: 809ms
  • Memory: 163792kb
  • [2023-10-03 02:06:05]
  • 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;
    }
    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";
}


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: 0ms
memory: 3636kb

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: 3692kb

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: 1ms
memory: 3892kb

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: 12ms
memory: 4516kb

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: 3612kb

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: 3696kb

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: 286ms
memory: 4392kb

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: 1ms
memory: 3584kb

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: 1ms
memory: 3888kb

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: 393ms
memory: 4460kb

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: 222ms
memory: 4476kb

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: 0ms
memory: 3700kb

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: 809ms
memory: 163792kb

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