QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#32866 | #884. Joining Treasure Hunt | AutumnKite | AC ✓ | 813ms | 6832kb | C++17 | 1.2kb | 2022-05-25 10:17:27 | 2022-05-25 10:17:29 |
Judging History
answer
#include <bits/stdc++.h>
const char name[] = "nsew";
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
char c;
std::cin >> c;
if (c == '?') {
a[i] = -1;
} else {
int x;
std::cin >> x;
a[i] = (std::find(name, name + 4, c) - name) * 7 + x - 1;
}
}
std::vector<int> b(m);
for (int i = 0; i < m; ++i) {
char c;
std::cin >> c;
if (c == '?') {
b[i] = -1;
} else {
int x;
std::cin >> x;
b[i] = (std::find(name, name + 4, c) - name) * 7 + x - 1;
}
}
const int C = 28;
std::vector<std::bitset<400000>> mask(C);
for (int i = 0; i < C; ++i) {
mask[i].set();
}
for (int i = 0; i < m; ++i) {
if (b[i] != -1) {
mask[b[i]].reset(i);
} else {
for (int j = 0; j < C; ++j) {
mask[j].reset(i);
}
}
}
std::bitset<400000> S;
S.set();
int ans = 0;
for (int i = 0; i < n; ++i) {
S <<= 1;
if (a[i] != -1) {
S |= mask[a[i]];
}
if (!S.test(m - 1)) {
++ans;
}
}
std::cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4452kb
input:
4 3 n 4 e 1 ? s 5 ? e 1 ?
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 3ms
memory: 4512kb
input:
4 3 n 4 e 1 w 3 s 5 ? e 1 ?
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 813ms
memory: 6832kb
input:
400000 200000 ? ? e 7 e 7 ? ? ? e 7 e 7 ? ? e 7 ? e 7 e 7 ? e 7 ? ? ? e 7 ? ? e 7 ? ? ? ? e 7 ? e 7 ? ? e 7 ? ? e 7 e 7 e 7 ? ? ? ? ? ? e 7 ? e 7 ? ? ? ? ? ? ? ? ? ? e 7 e 7 ? ? e 7 ? e 7 e 7 ? ? e 7 e 7 e 7 ? e 7 e 7 ? ? ? ? ? ? e 7 e 7 ? ? e 7 ? ? ? ? e 7 ? ? ? e 7 ? e 7 ? e 7 ? ? ? ? ? e 7 ? ? ? ...
output:
133037
result:
ok answer is '133037'
Test #4:
score: 0
Accepted
time: 693ms
memory: 5384kb
input:
200000 10000 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 n 1 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 n 1 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5...
output:
6786
result:
ok answer is '6786'
Test #5:
score: 0
Accepted
time: 658ms
memory: 5484kb
input:
200000 10000 e 1 s 1 w 1 n 2 e 2 ? w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 ? e 1 s 1 w 1 n 2 e 2 s 2 w 2 ? e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s 5 w 5 n 6 e 6 s 6 w 6 n 7 e 7 s 7 w 7 n 1 e 1 s 1 w 1 n 2 e 2 s 2 w 2 n 3 e 3 s 3 w 3 n 4 e 4 s 4 w 4 n 5 e 5 s...
output:
6786
result:
ok answer is '6786'
Test #6:
score: 0
Accepted
time: 300ms
memory: 5244kb
input:
100000 50000 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1...
output:
523
result:
ok answer is '523'
Test #7:
score: 0
Accepted
time: 577ms
memory: 5328kb
input:
200000 4 s 3 e 2 ? n 5 s 2 e 2 e 5 w 2 w 6 w 5 w 2 n 4 e 3 ? n 5 e 4 n 5 ? s 2 w 1 e 4 s 3 ? ? n 1 e 3 w 7 n 5 w 5 e 1 ? w 3 s 6 e 7 e 4 e 5 n 5 w 3 w 7 e 2 s 2 w 2 e 1 s 3 s 4 w 7 n 3 w 6 e 4 s 7 w 5 n 5 ? ? s 2 e 1 s 3 ? s 1 e 6 n 6 e 7 ? s 6 s 3 w 6 w 2 e 7 e 3 w 3 e 6 e 4 n 2 n 7 w 3 s 5 w 7 n 2...
output:
52
result:
ok answer is '52'
Test #8:
score: 0
Accepted
time: 588ms
memory: 5876kb
input:
200000 100000 ? e 6 e 7 n 5 e 5 w 4 w 1 e 3 e 3 n 6 n 6 w 1 e 2 e 6 s 4 s 2 e 4 s 6 w 6 e 6 n 2 e 1 n 5 s 5 e 3 e 4 w 7 n 1 s 6 n 6 n 5 s 6 s 2 w 7 e 6 e 4 e 4 n 1 ? w 2 n 1 n 3 e 2 w 1 e 1 s 6 w 7 s 1 e 2 e 3 e 3 e 7 s 1 e 2 w 1 w 6 s 1 s 7 e 4 e 1 s 1 w 5 ? s 5 n 4 w 2 ? e 3 n 6 n 2 s 4 s 1 n 7 n ...
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 588ms
memory: 5872kb
input:
200000 100000 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e 7 e ...
output:
100001
result:
ok answer is '100001'