QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198089 | #3516. Dungeon Crawler | Gamal74# | WA | 600ms | 4624kb | C++20 | 3.6kb | 2023-10-03 02:05:26 | 2023-10-03 02:05:26 |
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 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