QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198089#3516. Dungeon CrawlerGamal74#WA 600ms4624kbC++203.6kb2023-10-03 02:05:262023-10-03 02:05:26

Judging History

This is the latest submission verdict.

  • [2023-10-03 02:05:26]
  • Judged
  • Verdict: WA
  • Time: 600ms
  • Memory: 4624kb
  • [2023-10-03 02:05:26]
  • 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 match(nxt, v);
    }
    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();
    }
}

詳細信息

Test #1:

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

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

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: 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: 6ms
memory: 4508kb

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

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

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: 366ms
memory: 4356kb

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

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

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: 374ms
memory: 4624kb

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: 600ms
memory: 4444kb

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: -100
Wrong Answer
time: 0ms
memory: 3604kb

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 2

result:

wrong answer Expected not identical, but got 2