QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#198092 | #3516. Dungeon Crawler | Gamal74# | WA | 777ms | 163784kb | C++20 | 3.7kb | 2023-10-03 02:09:16 | 2023-10-03 02:09:17 |
Judging History
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