QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302433#7975. coneyislandhos_lyric#14 30ms4220kbC++144.6kb2024-01-10 21:13:222024-07-04 03:17:22

Judging History

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

  • [2024-07-04 03:17:22]
  • 评测
  • 测评结果:14
  • 用时:30ms
  • 内存:4220kb
  • [2024-01-10 21:13:22]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr int INF = 1001001001;

int C;
struct Data {
  int cnt[2], cost[2][2];
  Data() : cnt{}, cost{} {}
  void up() {
    swap(cnt[0], cnt[1]);
    ++cnt[0];
    int sub[2][2];
    memcpy(sub, cost, sizeof(cost));
    for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) {
      sub[x][y] += 0
        + ((x == 1) ? 1 : 0)
        + ((x == 0 && y == 1) ? C : 0)
      ;
    }
    for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) {
      int mn = INF;
      for (int xx = 0; xx < 2; ++xx) for (int yy = 0; yy < 2; ++yy) {
        if (y == 0 && xx == 1) continue;
        if (yy == 0 && x == 1) continue;
        chmin(mn, sub[yy ^ 1][xx ^ 1]);
      }
      cost[x][y] = mn;
    }
  }
};
ostream &operator<<(ostream &os, const Data &f) {
  return os << "(" << f.cnt[0] << "," << f.cnt[1] << "; " << f.cost[0][0] << "," << f.cost[0][1] << "," << f.cost[1][0] << "," << f.cost[1][1] << ")";
}
Data operator+(const Data &f, const Data &g) {
  Data h;
  for (int s = 0; s < 2; ++s) h.cnt[s] = f.cnt[s] + g.cnt[s];
  for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) h.cost[x][y] = f.cost[x][y] + g.cost[x][y];
  return h;
}
Data operator-(const Data &f, const Data &g) {
  Data h;
  for (int s = 0; s < 2; ++s) h.cnt[s] = f.cnt[s] - g.cnt[s];
  for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) h.cost[x][y] = f.cost[x][y] - g.cost[x][y];
  return h;
}


int N, M, Q;
vector<int> A, B;
vector<int> O, U, V, K;


namespace brute {
vector<vector<int>> graph;
Data solve(int u, int p) {
  Data f;
  for (const int v : graph[u]) if (p != v) {
    f = f + solve(v, u);
  }
  f.up();
// cerr<<u<<" "<<p<<": "<<f<<endl;
  return f;
}

vector<int> run() {
cerr<<"[brute::run]"<<endl;
  set<pair<int, int>> es;
  for (int i = 0; i < M; ++i) {
    es.insert(minmax(A[i], B[i]));
  }
  vector<int> anss;
  for (int q = 0; q < Q; ++q) {
    if (O[q] == 1) {
      es.insert(minmax(U[q], V[q]));
    } else if (O[q] == 2) {
      es.erase(minmax(U[q], V[q]));
    } else if (O[q] == 3) {
      int ans;
      if (K[q] % 2 != 0) {
        graph.assign(N, {});
        for (const auto &e : es) {
          graph[e.first].push_back(e.second);
          graph[e.second].push_back(e.first);
        }
        C = (K[q] + 1) / 2;
        const auto res = solve(U[q], -1);
        if (res.cnt[0] == res.cnt[1]) {
          ans = (res.cost[0][1] >= res.cnt[0]) ? 1 : 0;
        } else {
          ans = 0;
        }
      } else {
        ans = 1;
      }
      anss.push_back(ans);
    } else {
      assert(false);
    }
  }
  return anss;
}
}  // brute


int main() {
  // exper();
  
  for (; ~scanf("%d%d%d", &N, &M, &Q); ) {
    A.resize(M);
    B.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    O.assign(Q, -1);
    U.assign(Q, -1);
    V.assign(Q, -1);
    K.assign(Q, -1);
    for (int q = 0; q < Q; ++q) {
      scanf("%d", &O[q]);
      if (O[q] == 1 || O[q] == 2) {
        scanf("%d%d", &U[q], &V[q]);
        --U[q];
        --V[q];
      } else if (O[q] == 3) {
        scanf("%d%d", &U[q], &K[q]);
        --U[q];
      } else {
        assert(false);
      }
    }
    
    const auto anss = brute::run();
    for (const int ans : anss) {
      puts(ans ? "Bob" : "Alice");
    }
  }
  return 0;
}

詳細信息

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 3ms
memory: 3684kb

input:

100 82 2000
6 28
55 86
74 84
41 1
41 33
32 10
94 62
11 16
46 51
73 8
61 24
41 19
46 25
45 38
1 75
29 48
41 76
87 6
79 72
61 23
41 88
29 53
99 5
46 12
47 83
95 30
59 32
51 45
86 21
53 98
100 80
6 100
92 17
39 18
15 93
4 26
18 20
86 77
4 7
75 11
97 39
58 31
49 58
41 3
46 40
72 56
4 41
87 36
57 50
10 8...

output:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alic...

result:

ok 2000 tokens

Test #2:

score: 0
Accepted
time: 2ms
memory: 3664kb

input:

100 79 2000
46 8
100 92
56 70
46 95
23 99
63 74
42 3
58 78
27 36
89 4
33 25
53 22
41 59
66 1
9 32
77 76
100 38
60 85
69 5
58 43
72 49
10 17
26 48
99 30
95 19
44 89
60 88
69 61
45 53
75 14
62 81
13 33
89 26
42 16
43 13
99 31
7 18
62 65
91 80
85 28
28 42
20 24
94 35
70 55
37 15
35 21
3 12
45 83
63 57
...

output:

Alice
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Bob
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Bob
...

result:

ok 2000 tokens

Test #3:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

100 85 2000
25 99
84 90
80 84
93 50
20 70
72 14
19 73
37 54
79 1
20 13
63 2
50 52
81 66
80 68
10 7
85 51
1 49
96 69
75 25
68 27
25 65
77 79
78 91
19 29
84 5
22 11
14 4
53 18
40 12
37 47
46 34
92 36
75 96
5 76
19 57
9 64
56 16
6 21
31 86
49 98
93 3
13 59
100 23
39 10
8 67
55 28
56 53
75 81
72 61
37 4...

output:

Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Alice
Al...

result:

ok 2000 tokens

Test #4:

score: 0
Accepted
time: 3ms
memory: 3988kb

input:

100 89 2000
52 88
50 78
18 35
58 7
3 5
85 92
75 96
72 100
57 82
35 95
56 4
9 44
56 25
46 18
79 15
46 28
56 68
74 47
73 16
76 73
32 11
7 49
75 26
36 45
57 31
89 21
97 74
2 38
51 70
6 12
66 53
92 72
64 83
93 55
95 56
61 20
59 13
98 43
38 48
75 61
75 67
91 84
79 32
75 1
79 86
14 34
60 17
54 24
32 27
79...

output:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Al...

result:

ok 2000 tokens

Test #5:

score: 0
Accepted
time: 3ms
memory: 3700kb

input:

100 85 2000
76 47
18 17
73 13
100 81
18 16
91 51
35 98
80 89
4 19
89 74
71 75
46 10
16 53
54 3
43 61
47 30
90 87
45 56
91 23
34 28
91 70
100 29
94 96
55 4
81 64
54 76
95 62
31 90
9 5
87 27
12 86
81 34
59 94
8 44
29 36
21 40
40 50
36 65
77 43
69 97
86 57
74 15
64 92
100 35
52 4
17 25
5 10
71 78
100 2...

output:

Bob
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Bob
Bob
...

result:

ok 2000 tokens

Test #6:

score: 0
Accepted
time: 3ms
memory: 3724kb

input:

100 86 2000
69 32
48 45
45 19
93 95
75 1
61 36
15 34
71 42
34 81
63 30
24 71
58 94
8 63
46 37
76 65
7 24
61 13
94 64
2 11
1 9
90 23
61 98
53 87
22 91
94 67
58 53
62 90
52 92
10 89
20 15
22 58
39 51
74 68
65 83
61 48
82 59
33 7
31 16
89 5
46 84
52 20
56 75
14 74
95 12
31 73
26 43
91 57
28 10
85 88
8 ...

output:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alic...

result:

ok 2000 tokens

Test #7:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

100 88 2000
76 54
50 48
42 25
22 15
21 76
4 6
16 55
100 19
40 77
3 85
36 64
7 65
88 39
36 28
94 10
77 34
21 7
87 22
61 17
94 47
47 26
89 92
91 66
59 67
90 5
41 44
90 49
72 40
91 1
36 38
94 36
75 71
51 2
90 46
1 95
44 31
47 60
64 75
70 58
18 76
40 84
19 3
73 29
61 91
72 16
3 81
23 56
51 4
50 30
33 43...

output:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alic...

result:

ok 2000 tokens

Test #8:

score: 0
Accepted
time: 3ms
memory: 4000kb

input:

100 90 2000
81 80
49 24
93 46
69 23
35 20
12 74
36 1
100 84
61 34
27 46
61 97
55 92
72 12
35 10
37 65
70 37
39 81
67 83
61 2
23 72
2 9
22 41
32 14
38 11
13 27
37 69
14 49
26 19
44 42
47 76
70 90
5 98
96 99
100 79
70 50
35 29
45 16
19 31
15 54
59 67
49 85
74 33
65 26
56 96
48 88
28 51
36 52
5 100
28 ...

output:

Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Al...

result:

ok 2000 tokens

Test #9:

score: 0
Accepted
time: 2ms
memory: 3984kb

input:

100 84 2000
41 95
99 6
72 97
82 4
36 1
32 68
17 81
75 70
59 42
75 77
5 21
72 11
7 83
3 29
84 65
3 58
64 28
17 74
54 63
61 22
47 88
64 2
10 9
16 43
38 96
35 25
12 50
39 27
25 56
90 66
84 86
84 37
22 16
79 41
47 15
48 90
87 33
39 55
64 19
36 52
36 23
31 99
73 3
97 94
59 32
60 47
11 80
100 93
84 98
5 3...

output:

Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Al...

result:

ok 2000 tokens

Test #10:

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

input:

100 86 2000
61 88
21 12
76 5
68 90
6 76
63 30
71 56
32 59
95 2
93 100
13 51
12 92
76 23
42 16
3 78
41 83
21 81
42 58
30 71
74 66
50 60
29 79
96 29
18 36
68 89
96 34
67 17
20 54
31 61
16 84
44 41
8 22
99 87
9 4
40 20
9 26
83 91
23 37
55 93
39 35
5 75
54 73
95 31
37 85
100 38
26 28
72 43
62 7
99 45
23...

output:

Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Bob
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Alice
...

result:

ok 2000 tokens

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 13
Accepted
time: 0ms
memory: 3684kb

input:

200 171 2000
29 151
55 127
16 192
79 166
138 145
198 45
19 130
37 172
136 37
197 183
136 116
171 112
132 21
118 47
55 75
150 41
47 74
7 97
143 106
129 197
39 124
160 63
134 182
30 173
64 66
119 59
47 104
172 111
69 90
28 167
61 171
70 148
23 17
93 143
93 89
79 108
60 44
33 50
81 92
30 40
115 120
112...

output:

Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
...

result:

ok 2000 tokens

Test #12:

score: 0
Accepted
time: 4ms
memory: 3740kb

input:

200 181 2000
56 26
121 183
92 77
12 107
190 176
6 57
167 113
127 115
161 193
29 111
38 78
112 141
96 44
57 84
30 31
16 179
30 86
169 181
52 148
8 57
46 160
17 34
61 140
72 86
128 76
82 50
21 103
101 98
46 52
9 200
148 68
100 70
26 86
67 72
165 112
112 177
52 75
88 24
182 97
164 118
75 21
198 131
92 ...

output:

Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alic...

result:

ok 2000 tokens

Test #13:

score: 0
Accepted
time: 4ms
memory: 3712kb

input:

200 184 2000
127 186
21 189
145 124
63 26
185 196
135 190
44 147
70 77
17 25
180 194
42 14
138 166
137 170
44 32
132 83
151 49
59 34
198 141
88 13
156 132
73 2
84 110
134 122
6 182
137 185
127 69
70 109
164 23
17 41
53 120
13 129
184 197
7 181
137 157
70 96
132 125
23 89
11 90
55 116
102 117
133 82
...

output:

Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Bob
Al...

result:

ok 2000 tokens

Test #14:

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

input:

200 168 2000
18 155
177 186
200 101
31 137
146 147
78 53
89 42
88 72
130 59
144 95
148 66
19 56
129 51
140 151
63 46
91 10
187 161
62 114
60 105
80 200
171 165
29 45
182 117
43 146
162 48
97 176
180 12
168 69
24 119
149 133
74 38
34 97
13 84
152 81
170 100
66 120
160 19
42 73
161 64
63 75
171 136
14...

output:

Alice
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Bo...

result:

ok 2000 tokens

Test #15:

score: -13
Wrong Answer
time: 2ms
memory: 3708kb

input:

200 182 2000
67 189
134 137
118 86
190 133
48 74
199 72
102 143
98 88
164 40
97 58
16 46
199 19
14 67
125 79
32 44
33 156
177 73
57 26
43 106
24 174
135 54
158 179
59 138
199 139
147 2
148 184
17 53
117 120
83 162
6 123
123 43
97 129
111 170
133 3
113 104
114 196
128 113
133 127
114 78
115 38
99 84
...

output:

Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bo...

result:

wrong answer 138th words differ - expected: 'Bob', found: 'Alice'

Subtask #3:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 25ms
memory: 3928kb

input:

2000 1890 2000
1212 557
338 550
270 153
1622 738
1793 1582
269 24
1631 1087
884 650
993 737
1193 676
1107 1858
1927 1456
1928 985
332 888
893 212
1393 1530
1635 7
1300 1955
437 260
283 1616
912 544
1806 106
431 656
980 182
173 1786
714 342
884 1595
1658 150
117 725
642 1931
1608 1213
972 726
193 927...

output:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
...

result:

ok 1013 tokens

Test #22:

score: 0
Accepted
time: 25ms
memory: 3908kb

input:

2000 1880 2000
384 1996
933 1898
229 67
754 1718
537 1884
586 1568
1988 83
665 839
1689 845
184 1351
591 1459
83 1433
1354 858
516 1049
80 1339
131 58
303 1808
229 1144
371 1217
108 1062
1681 1407
389 1851
937 570
139 1324
266 639
266 1549
1068 832
1757 1969
1285 560
524 881
506 42
959 53
1863 1091
...

output:

Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Bo...

result:

ok 1012 tokens

Test #23:

score: 0
Accepted
time: 30ms
memory: 3928kb

input:

2000 1900 2000
1794 441
1243 659
70 797
195 1635
554 1259
1117 1395
1346 41
377 155
734 1542
179 649
1872 345
1340 1942
1794 480
1518 694
133 1733
1173 640
496 928
548 445
1292 1176
1363 1645
133 1350
1794 1873
1409 632
591 1160
820 1051
1741 1428
247 1445
1794 490
863 1360
1840 665
1353 1046
1606 5...

output:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bo...

result:

ok 1010 tokens

Test #24:

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

input:

2000 1880 2000
469 203
577 386
1342 772
1216 593
819 1667
839 536
1751 1471
439 18
1751 248
1979 139
402 297
1165 851
430 1172
1950 1618
724 1284
1724 875
795 1417
783 1639
1938 226
1227 69
1531 1890
714 419
1861 1915
1540 191
1938 1514
1830 1260
859 1609
129 879
193 619
651 296
1718 425
958 1536
60...

output:

Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
...

result:

ok 1015 tokens

Test #25:

score: 0
Accepted
time: 29ms
memory: 3928kb

input:

2000 1880 2000
801 1735
327 1934
39 1942
460 124
98 526
1654 174
1640 1330
951 1715
508 272
1654 1434
818 296
994 1772
1041 1120
1704 855
1097 1163
281 291
1312 1008
837 1762
1081 1526
651 525
1533 1448
460 1219
837 369
359 1872
1205 995
1202 1544
800 1696
341 565
1039 720
155 844
998 1830
883 1073
...

output:

Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Bob
Bob
Bob
Bob
Bo...

result:

ok 1015 tokens

Test #26:

score: 0
Accepted
time: 27ms
memory: 3932kb

input:

2000 1880 2000
1233 1970
838 945
790 274
948 933
1454 1528
1652 1622
655 910
1636 1452
1233 1818
1025 682
380 656
728 1748
1011 1578
99 1181
718 581
112 805
1525 1724
1011 1988
728 1479
360 1387
1008 1058
480 1459
437 802
1233 1992
381 1739
808 642
1057 1238
1747 1624
1597 1182
1672 1892
1525 67
736...

output:

Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
...

result:

ok 1014 tokens

Test #27:

score: 0
Accepted
time: 23ms
memory: 3928kb

input:

2000 1886 2000
817 522
1131 114
886 1243
1040 1344
118 869
1649 282
663 758
1561 1203
42 1717
1311 547
200 460
1096 1253
826 1637
1402 1307
804 483
974 650
1440 641
1146 229
974 1100
510 6
1066 1242
870 1497
587 4
845 584
974 1055
424 1148
457 1431
127 473
974 1503
1071 579
712 792
1458 1821
1599 34...

output:

Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Bob
...

result:

ok 1011 tokens

Test #28:

score: 0
Accepted
time: 28ms
memory: 4220kb

input:

2000 1880 2000
1692 419
1443 1832
1957 1198
263 641
1064 1787
1467 815
857 1855
232 166
254 874
698 1902
1262 499
1763 702
121 771
1682 1587
1682 1268
956 54
254 370
834 1061
1131 1287
1285 836
1763 503
1197 1444
633 257
1282 795
1799 193
156 529
1483 573
663 398
958 880
1276 1641
1659 549
1158 125
...

output:

Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Bob
Bo...

result:

ok 1016 tokens

Test #29:

score: 0
Accepted
time: 28ms
memory: 3976kb

input:

2000 1894 2000
1014 835
757 1452
264 1595
1473 1861
1288 836
1938 1348
498 1706
1321 1571
1453 964
1113 842
1187 861
1314 743
1662 1414
1951 1362
726 1266
99 24
1989 1876
632 1144
151 1290
214 281
1967 161
824 900
1600 951
763 1878
481 1504
727 685
331 1825
7 182
1950 1983
264 687
533 1606
1751 1588...

output:

Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
...

result:

ok 1007 tokens

Test #30:

score: 0
Accepted
time: 29ms
memory: 4156kb

input:

2000 1880 2000
258 1347
600 1512
1185 1795
527 1349
82 891
292 145
1412 119
988 143
1006 193
976 1807
1506 205
1529 273
1185 870
1565 1057
806 1776
1793 1122
118 1309
795 627
1720 1509
1111 1170
950 697
1758 887
768 79
1312 1697
1038 1200
317 1664
1111 250
424 166
1529 1075
1506 7
1162 150
1758 362
...

output:

Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Bo...

result:

ok 1014 tokens

Subtask #4:

score: 0
Time Limit Exceeded

Test #31:

score: 0
Time Limit Exceeded

input:

50000 49880 20000
48314 21512
22153 12169
41488 42607
40229 41306
46264 28965
25173 26971
10383 46046
12460 40491
39907 3938
38678 10601
44612 9518
47459 40583
41078 31510
28311 20714
48314 14317
39657 18800
48314 13702
3127 22586
44612 19422
34192 11134
27163 4980
18592 29422
32962 18856
46707 2976...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #41:

score: 0
Time Limit Exceeded

input:

50000 49880 20000
25303 14342
14869 40179
21130 16220
24316 1709
17034 34229
30864 5296
3377 39615
7965 4758
45366 46099
20621 30122
11921 21129
23336 3391
49502 33595
38205 24561
16625 17058
4643 31243
43549 4838
14799 15012
43454 49265
12739 34594
43197 15991
28223 34847
45479 23973
41255 13540
20...

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #51:

score: 0
Time Limit Exceeded

input:

100000 99938 100000
26438 1998
89535 89756
70297 55360
82670 83756
93993 77139
94699 21163
45884 56882
5737 53295
62873 34215
1522 27236
30627 53486
81399 26563
9209 24434
23031 5002
94699 4551
98173 19852
52146 13350
63659 39283
63680 24484
67720 35030
53166 13805
61178 2860
4599 9418
69603 20505
8...

output:


result:


Subtask #7:

score: 0
Time Limit Exceeded

Test #61:

score: 0
Time Limit Exceeded

input:

100000 99880 100000
87456 56758
21039 93866
26684 26928
36261 38646
93837 81169
36296 6353
88166 12770
96349 79152
60764 55084
67648 76473
67261 81697
1338 12473
36261 24850
64931 59526
7612 4920
37210 86707
11909 71904
28413 92888
50434 86391
84363 85522
56085 64977
94695 65626
87341 83127
38204 33...

output:


result:


Subtask #8:

score: 0
Time Limit Exceeded

Test #71:

score: 0
Time Limit Exceeded

input:

100000 99880 100000
80697 25247
76841 47922
66709 88229
73265 29962
13180 20319
7033 54171
48021 24356
98808 61348
35961 92937
54442 42820
81432 64668
98653 18142
55715 49600
60985 28959
65046 4093
69598 22205
8119 66290
77738 20602
43567 62376
99070 22510
58039 57749
6112 67601
90321 78734
26200 73...

output:


result:


Subtask #9:

score: 0
Time Limit Exceeded

Test #81:

score: 0
Time Limit Exceeded

input:

200000 199880 200000
168914 47550
82712 187984
39807 122144
130242 14456
23948 60014
117395 33782
5841 143360
187633 129471
131245 172304
158977 106660
170354 46978
112953 163046
115136 149721
73220 13076
159876 149376
150989 54960
165232 30782
88995 101519
68939 49297
182393 32854
11939 160679
8819...

output:


result:


Subtask #10:

score: 0
Time Limit Exceeded

Test #91:

score: 0
Time Limit Exceeded

input:

200000 199880 200000
134083 139042
140377 118787
54058 177797
152488 166148
198441 48360
42832 50127
155051 185186
51187 59442
118950 160003
32770 17126
149739 27962
198441 167736
178483 69498
112923 130588
149787 50817
96021 88669
59657 69190
194397 11071
79331 190502
188682 55200
173317 76026
1742...

output:


result: