QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#622779 | #2364. Endgame | AngelOlan | WA | 47ms | 13224kb | C++20 | 1.7kb | 2024-10-09 05:30:04 | 2024-10-09 05:30:05 |
Judging History
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'