QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622779#2364. EndgameAngelOlanWA 47ms13224kbC++201.7kb2024-10-09 05:30:042024-10-09 05:30:05

Judging History

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

  • [2024-10-09 05:30:05]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:13224kb
  • [2024-10-09 05:30:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// Pura Gente del Coach Moy
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

#define pb push_back
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define ROF(i, a, b) for (int i = (int)a - 1; i >= (int)b; --i)
#define ENDL '\n'

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r) {
  return uniform_int_distribution<int>(l, r)(rng);
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  
  int n, ax, ay, bx, by;
  cin >> n >> ax >> ay >> bx >> by;
  
  set<pi> moves;
  FOR (i, 0, n) {
    int dx, dy;
    cin >> dx >> dy;
    moves.insert({dx, dy});
  }
  
  auto check = [&](int x, int y) -> bool {
    if (x == bx && y == by) return true;
    for (auto &[dx, dy] : moves) {
      int xx = x + dx, yy = y + dy;
      if (xx <= 0 || xx > n || yy <= 0 || y > n) continue;
      if (xx == bx && yy == by) return true;
      if (moves.count(make_pair(bx - xx, by - yy))) return true;
    }
    return false;
  };

  if (check(ax, ay)) {
    cout << "Alice wins" << ENDL;
    return 0;
  }

  {
    set<pi> new_moves;
    for (auto &[dx, dy] : moves) new_moves.insert({-dx, -dy});
    swap(moves, new_moves);
  }

  if (n <= 5000) {
    FOR (x, 1, n + 1) FOR (y, 1, n + 1) if (!check(x, y)) {
      cout << "tie " << x << ' ' << y << ENDL;
      return 0;
    }
    cout << "Bob wins" << ENDL;
    return 0;
  }

  int k = 500;
  FOR (i, 0, k) {
    int x = rnd(1, n), y = rnd(1, n);
    if (!check(x, y)) {
      cout << "tie " << x << ' ' << y << ENDL;
      return 0;
    }
  }
  cout << "Bob wins" << ENDL;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

3
2 3
1 3
1 0
0 -1
1 -1

output:

Bob wins

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

3
3 3
1 1
1 0
1 1
0 1

output:

Bob wins

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

3
2 2
3 1
-1 0
-1 1
0 1

output:

Bob wins

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

5
2 1
1 2
-2 2
1 -1
1 1
2 2
3 3

output:

tie 1 1

result:

ok 

Test #5:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2
1 1
1 2
1 -1
1 1

output:

tie 1 1

result:

ok 

Test #6:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

3
1 2
2 1
2 -2
-1 1
-2 2

output:

tie 1 1

result:

ok 

Test #7:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

2
2 2
1 1
1 1
1 0

output:

tie 1 2

result:

ok 

Test #8:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

2
1 1
2 2
-1 -1
1 0

output:

tie 1 2

result:

ok 

Test #9:

score: 0
Accepted
time: 47ms
memory: 13196kb

input:

100000
2 100000
1 100000
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0
32 0
33 0
34 0
35 0
36 0
37 0
38 0
39 0
40 0
41 0
42 0
43 0
44 0
45 0
46 0
47 0
48 0
49 0
50 0
51 0
52 0
53 0
54 0
55 0
56 0
57 0...

output:

tie 11399 16491

result:

ok 

Test #10:

score: 0
Accepted
time: 41ms
memory: 12944kb

input:

100000
2 1
1 1
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0
32 0
33 0
34 0
35 0
36 0
37 0
38 0
39 0
40 0
41 0
42 0
43 0
44 0
45 0
46 0
47 0
48 0
49 0
50 0
51 0
52 0
53 0
54 0
55 0
56 0
57 0
58 0
59 0...

output:

tie 42641 44405

result:

ok 

Test #11:

score: 0
Accepted
time: 39ms
memory: 12996kb

input:

100000
1 2
1 1
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59...

output:

tie 43645 45654

result:

ok 

Test #12:

score: 0
Accepted
time: 45ms
memory: 13004kb

input:

100000
100000 2
100000 1
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57...

output:

tie 41820 64181

result:

ok 

Test #13:

score: 0
Accepted
time: 40ms
memory: 13224kb

input:

100000
2 2
1 1
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0
32 0
33 0
34 0
35 0
36 0
37 0
38 0
39 0
40 0
41 0
42 0
43 0
44 0
45 0
46 0
47 0
48 0
49 0
50 0
51 0
52 0
53 0
54 0
55 0
56 0
57 0
58 0
59 0...

output:

tie 67610 47884

result:

ok 

Test #14:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

2
2 1
1 1
0 -1
1 -1

output:

tie 1 2

result:

ok 

Test #15:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

3
2 3
3 3
0 1
-2 2
-1 2

output:

tie 1 1

result:

ok 

Test #16:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

4
2 4
4 1
3 -3
2 0
-1 0
3 0

output:

Alice wins

result:

ok 

Test #17:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

5
4 2
5 2
-1 -1
2 -1
3 0
4 3
-2 -2

output:

tie 1 1

result:

ok 

Test #18:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

6
4 3
3 4
-4 -4
-3 -1
0 3
-3 0
3 -2
5 -4

output:

tie 1 1

result:

ok 

Test #19:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

7
4 6
2 4
-3 2
-1 -5
2 -6
3 -2
-5 4
2 6
4 5

output:

tie 1 1

result:

ok 

Test #20:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

8
5 3
8 6
-5 5
3 -2
5 -7
2 7
4 4
-4 -5
-2 -3
-2 6

output:

tie 1 1

result:

ok 

Test #21:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

9
6 1
6 4
-6 -6
-5 6
-5 4
-2 1
-4 -4
-3 -6
7 2
-1 5
3 -6

output:

tie 1 1

result:

ok 

Test #22:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

10
7 8
1 4
6 -7
-7 9
-2 2
-8 -3
7 5
0 -2
8 9
8 -4
7 2
9 -2

output:

tie 1 1

result:

ok 

Test #23:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

50
42 20
46 50
-29 -46
-35 42
3 -42
-21 -14
-31 20
24 -14
33 12
-28 47
-46 -9
-27 -35
14 -3
-8 -49
18 -22
-48 44
25 39
26 22
-23 -26
-8 33
31 19
-31 -31
-8 -32
-10 19
-34 17
-13 -39
31 -22
-3 30
19 -1
35 41
4 7
-1 45
-38 41
-24 -19
4 -30
-9 -1
-37 34
-38 -16
34 39
-47 15
9 15
-20 -4
4 -7
13 5
-9 -19...

output:

tie 1 1

result:

ok 

Test #24:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

5
2 1
5 1
-4 3
-3 0
0 4
3 -4
4 -2

output:

Alice wins

result:

ok 

Test #25:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

10
7 7
5 2
-9 2
-5 -3
-3 -6
-2 9
1 1
2 -2
4 -5
4 -4
5 1
9 -2

output:

Alice wins

result:

ok 

Test #26:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

30
3 5
2 29
-27 17
-20 -9
-20 18
-18 3
-18 18
-17 26
-14 -17
-14 22
-10 -20
-8 19
-7 -11
-7 28
-3 -19
-3 -5
-3 1
4 29
5 -6
7 5
12 18
17 19
17 22
18 -27
22 -19
24 -20
25 -29
25 9
28 -29
28 -16
28 5
28 9

output:

Alice wins

result:

ok 

Test #27:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

83
46 11
67 38
-79 -8
-77 30
-75 -54
-74 44
-69 -52
-69 -13
-68 -17
-65 -35
-62 44
-61 -20
-60 -24
-60 43
-58 -72
-58 76
-55 -55
-52 -47
-50 -18
-47 53
-46 64
-44 21
-41 -70
-41 82
-38 31
-37 28
-36 43
-35 16
-32 -14
-30 -64
-29 -22
-28 -14
-27 -13
-26 -52
-26 74
-24 -29
-22 35
-20 11
-20 64
-16 -11...

output:

tie 1 1

result:

ok 

Test #28:

score: -100
Wrong Answer
time: 0ms
memory: 3624kb

input:

99
20 65
8 69
-98 -81
-98 42
-93 -19
-91 -40
-91 80
-89 -69
-89 -1
-88 32
-88 95
-86 68
-86 90
-85 86
-82 80
-81 54
-78 -3
-75 75
-73 -67
-73 5
-73 19
-73 69
-68 13
-67 33
-64 70
-60 95
-58 -53
-58 93
-57 -53
-57 16
-56 -42
-43 46
-40 -20
-34 24
-29 -60
-26 -49
-26 40
-25 -9
-25 25
-24 19
-13 34
-10...

output:

Alice wins

result:

wrong answer Author claims 'alice', but judge claims 'tie'