QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#422454#7303. City UniteddayuxWA 76ms62328kbC++141.5kb2024-05-27 14:44:332024-05-27 14:44:34

Judging History

你现在查看的是最新测评结果

  • [2024-05-27 14:44:34]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:62328kb
  • [2024-05-27 14:44:33]
  • 提交

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'