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