QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#422454 | #7303. City United | dayux | WA | 76ms | 62328kb | C++14 | 1.5kb | 2024-05-27 14:44:33 | 2024-05-27 14:44:34 |
Judging History
answer
#include <bits/stdc++.h>
const int maxn = 50, maxd = 12, mod = 4;
std::array<int, maxn + 1> e;
std::array<std::array<std::array<short, 1 << maxd>, 1 << maxd>, 2> f;
void inc(short &x, short y) {
if ((x += y) >= mod) {
x -= mod;
}
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
e[std::max(u, v)] |= 1 << (std::abs(u - v) - 1);
}
f[0 & 1][0][0] = 1;
int all = (1 << maxd) - 1;
for (int i = 1; i <= n; ++i) {
for (int S = 0; S <= all; ++S) {
for (int T = S; ; T = (T - 1) & S) {
int R = S ^ T;
f[i & 1][T][R] = 0;
if (T == 0) {
break;
}
}
}
for (int S = 0; S <= all; ++S) {
for (int T = S; ; T = (T - 1) & S) {
int R = S ^ T;
inc(f[i & 1][(T << 1) & all][(R << 1) & all], f[(i - 1) & 1][T][R]);
if ((e[i] & R) == 0) {
inc(f[i & 1][(T << 1 | 1) & all][(R << 1) & all], f[(i - 1) & 1][T][R]);
}
if ((e[i] & T) == 0) {
inc(f[i & 1][(T << 1) & all][(R << 1 | 1) & all], f[(i - 1) & 1][T][R]);
}
if (T == 0) {
break;
}
}
}
}
short ans = 0;
for (int S = 0; S <= all; ++S) {
for (int T = S; ; T = (T - 1) & S) {
inc(ans, f[n & 1][T][S ^ T]);
if (T == 0) {
break;
}
}
}
std::cout << ans / 2 << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 16ms
memory: 62268kb
input:
3 2 1 2 2 3
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 16ms
memory: 62328kb
input:
3 3 1 2 2 3 3 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 76ms
memory: 62212kb
input:
15 31 9 5 14 5 2 7 5 15 11 14 11 9 2 6 3 4 12 1 6 8 3 5 11 10 15 6 4 1 1 2 8 9 6 12 14 10 13 2 4 5 3 8 3 15 11 6 7 5 4 6 11 2 13 15 3 2 8 4 6 13 7 10
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 64ms
memory: 62284kb
input:
15 92 10 9 15 7 11 1 7 2 12 10 1 12 4 13 1 4 11 5 1 2 4 3 1 9 15 4 11 7 14 1 8 7 8 12 7 4 10 14 7 13 6 13 4 12 11 10 13 8 13 15 10 7 2 14 12 13 14 5 8 4 12 9 7 9 15 10 10 4 11 15 13 10 6 15 8 9 2 8 11 12 5 4 1 6 2 9 10 1 5 6 14 12 5 13 5 10 6 9 15 8 12 15 10 2 5 7 4 6 2 11 12 3 15 9 9 3 3 10 5 2 12 ...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 72ms
memory: 62272kb
input:
15 80 5 10 10 13 13 4 4 2 6 10 8 6 13 7 13 9 9 5 6 13 6 3 13 14 10 12 8 3 8 13 9 1 7 5 14 6 14 10 6 9 11 14 7 10 13 15 7 9 14 7 8 1 10 3 11 6 15 7 12 8 3 13 6 2 6 7 13 5 7 3 11 8 3 5 2 5 15 2 7 12 1 14 11 1 1 10 10 4 4 14 2 9 12 5 15 8 8 5 1 13 1 12 9 14 14 2 1 3 14 5 10 15 3 15 1 7 1 5 6 15 8 9 2 7...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 63ms
memory: 62292kb
input:
15 45 13 15 3 15 5 4 15 14 6 10 2 3 10 11 9 8 8 7 10 4 9 2 3 8 15 2 2 6 15 9 6 15 10 7 8 2 5 6 14 10 12 10 8 1 11 3 3 12 2 1 11 15 11 5 2 7 1 11 8 4 1 6 14 5 5 2 13 1 7 11 4 12 12 14 15 5 7 5 10 2 4 7 13 2 4 14 12 1 12 11
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 67ms
memory: 62272kb
input:
15 48 5 14 11 1 6 8 10 3 10 6 3 4 3 8 15 3 10 15 2 11 5 15 7 10 7 14 5 10 2 9 9 3 11 4 11 7 12 5 9 10 10 14 10 2 13 11 2 8 10 13 2 3 7 12 13 3 10 8 12 10 15 12 4 7 9 13 7 13 5 7 2 13 11 14 9 15 6 15 8 12 2 6 1 13 3 14 4 15 5 3 6 3 4 10 2 7
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 71ms
memory: 62328kb
input:
15 104 9 1 11 4 11 6 2 14 8 3 10 6 1 4 8 5 4 15 10 4 12 4 14 11 7 9 12 15 1 10 13 14 9 14 1 6 4 2 2 9 5 10 14 10 2 10 12 6 3 10 9 5 1 7 12 14 5 2 10 13 7 6 6 8 10 15 8 14 14 5 9 12 1 3 12 10 10 9 6 14 8 7 8 11 10 11 13 6 11 5 12 3 3 13 11 9 7 12 8 1 11 12 15 8 8 12 9 13 8 9 14 7 7 11 3 7 3 11 14 3 1...
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 59ms
memory: 62272kb
input:
15 102 9 8 7 5 2 3 5 14 15 7 7 9 15 11 14 15 13 7 4 1 3 6 8 14 4 7 12 7 10 1 13 5 2 8 8 12 10 9 5 3 14 1 10 8 10 14 13 3 6 9 6 12 1 3 10 5 2 15 8 13 8 4 1 7 6 13 5 2 14 9 6 2 6 11 2 1 11 9 1 12 6 14 14 13 10 7 1 6 3 7 12 10 12 13 12 5 12 2 12 14 4 9 3 9 13 11 11 10 5 1 10 15 8 7 6 7 13 2 6 5 8 6 11 ...
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 69ms
memory: 62216kb
input:
15 104 3 4 11 8 5 13 8 7 9 4 7 11 3 2 6 11 10 4 9 7 3 12 11 2 1 11 5 12 1 10 5 6 6 7 2 10 12 14 1 14 13 11 1 3 9 8 6 13 10 14 1 7 11 10 11 14 6 8 11 9 12 13 15 7 9 3 13 4 3 14 12 7 2 4 10 9 10 7 2 1 15 9 6 15 12 9 14 7 7 3 12 15 11 3 3 10 4 6 5 11 10 5 11 15 13 10 6 1 10 12 12 11 4 7 10 8 4 1 13 2 3...
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: -100
Wrong Answer
time: 67ms
memory: 62208kb
input:
15 91 1 11 15 14 14 11 5 10 4 6 6 10 11 3 14 5 15 10 3 2 11 5 9 13 11 12 15 5 13 12 3 7 2 4 12 2 10 13 7 8 9 11 8 11 3 5 3 10 8 3 14 10 2 7 12 15 3 6 6 9 8 4 6 2 8 1 7 10 5 1 7 6 4 1 10 2 11 4 1 13 12 14 11 6 9 3 9 5 14 3 14 9 8 14 9 8 4 3 1 7 15 3 13 3 4 15 15 8 5 4 14 1 10 9 13 7 12 7 7 15 9 2 6 1...
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'