QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100498 | #5565. Mirror Madness | PetroTarnavskyi# | AC ✓ | 221ms | 122816kb | C++17 | 1.5kb | 2023-04-26 17:05:14 | 2023-04-26 17:05:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int MAX = 1 << 20;
vector<pair<int, int>> vec[2][2 * MAX];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> x(n), y(n);
FOR(i, 0, n) {
cin >> x[i] >> y[i];
}
x.push_back(x[0]);
y.push_back(y[0]);
FOR(i, 0, n) {
int xMin = x[i], xMax = x[i + 1], yMin = y[i], yMax = y[i + 1];
if (xMin > xMax) {
swap(xMin, xMax);
}
if (yMin > yMax) {
swap(yMin, yMax);
}
int v = xMin == xMax;
FOR(xx, xMin, xMax + 1) {
FOR(yy, yMin, yMax + 1) {
if ((xx & 1) ^ (yy & 1)) {
vec[0][xx - yy + MAX].emplace_back(xx, v);
vec[1][xx + yy].emplace_back(xx, v);
}
}
}
}
FOR(i, 0, 2) {
FOR(j, 0, 2 * MAX) {
sort(ALL(vec[i][j]));
}
}
int xs, ys;
cin >> xs >> ys;
int vx = 1, vy = 1;
while (m--) {
int i = vx != vy, j = i == 0 ? xs - ys + MAX : xs + ys;
auto it = lower_bound(ALL(vec[i][j]), make_pair(xs, 0));
if (vx == 1) {
it++;
}
else {
it--;
}
xs = it->first;
ys = i == 0 ? xs + MAX - j : j - xs;
if (it->second) {
vx *= -1;
}
else {
vy *= -1;
}
cout << xs << " " << ys << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 29ms
memory: 101732kb
input:
4 6 0 0 10 0 10 10 0 10 1 0
output:
10 9 9 10 0 1 1 0 10 9 9 10
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 28ms
memory: 101732kb
input:
10 10 -2 -2 8 -2 8 8 4 8 4 0 2 0 2 6 -4 6 -4 2 -2 2 4 1
output:
8 5 5 8 4 7 8 3 3 -2 -4 5 -3 6 2 1 -1 -2 -2 -1
result:
ok 10 lines
Test #3:
score: 0
Accepted
time: 22ms
memory: 101636kb
input:
20 50 0 0 18 0 18 10 16 10 16 2 14 2 14 10 12 10 12 2 10 2 10 10 8 10 8 2 6 2 6 10 4 10 4 2 2 2 2 10 0 10 1 0
output:
3 2 5 0 7 2 9 0 11 2 13 0 15 2 17 0 18 1 16 3 18 5 16 7 18 9 17 10 16 9 18 7 16 5 18 3 15 0 12 3 14 5 12 7 14 9 13 10 12 9 14 7 12 5 14 3 11 0 8 3 10 5 8 7 10 9 9 10 8 9 10 7 8 5 10 3 7 0 4 3 6 5 4 7 6 9 5 10 4 9 6 7 4 5 6 3 3 0 0 3
result:
ok 50 lines
Test #4:
score: 0
Accepted
time: 143ms
memory: 110564kb
input:
1996 500000 0 0 1994 0 1994 1000 1992 1000 1992 2 1990 2 1990 1000 1988 1000 1988 2 1986 2 1986 1000 1984 1000 1984 2 1982 2 1982 1000 1980 1000 1980 2 1978 2 1978 1000 1976 1000 1976 2 1974 2 1974 1000 1972 1000 1972 2 1970 2 1970 1000 1968 1000 1968 2 1966 2 1966 1000 1964 1000 1964 2 1962 2 1962 ...
output:
3 2 5 0 7 2 9 0 11 2 13 0 15 2 17 0 19 2 21 0 23 2 25 0 27 2 29 0 31 2 33 0 35 2 37 0 39 2 41 0 43 2 45 0 47 2 49 0 51 2 53 0 55 2 57 0 59 2 61 0 63 2 65 0 67 2 69 0 71 2 73 0 75 2 77 0 79 2 81 0 83 2 85 0 87 2 89 0 91 2 93 0 95 2 97 0 99 2 101 0 103 2 105 0 107 2 109 0 111 2 113 0 115 2 117 0 119 2...
result:
ok 500000 lines
Test #5:
score: 0
Accepted
time: 166ms
memory: 119224kb
input:
333332 500000 0 0 333330 0 333330 4 333328 4 333328 2 333326 2 333326 4 333324 4 333324 2 333322 2 333322 4 333320 4 333320 2 333318 2 333318 4 333316 4 333316 2 333314 2 333314 4 333312 4 333312 2 333310 2 333310 4 333308 4 333308 2 333306 2 333306 4 333304 4 333304 2 333302 2 333302 4 333300 4 333...
output:
3 2 5 0 7 2 9 0 11 2 13 0 15 2 17 0 19 2 21 0 23 2 25 0 27 2 29 0 31 2 33 0 35 2 37 0 39 2 41 0 43 2 45 0 47 2 49 0 51 2 53 0 55 2 57 0 59 2 61 0 63 2 65 0 67 2 69 0 71 2 73 0 75 2 77 0 79 2 81 0 83 2 85 0 87 2 89 0 91 2 93 0 95 2 97 0 99 2 101 0 103 2 105 0 107 2 109 0 111 2 113 0 115 2 117 0 119 2...
result:
ok 500000 lines
Test #6:
score: 0
Accepted
time: 24ms
memory: 101752kb
input:
340 3000 2 0 2 -2 4 -2 4 0 6 0 6 2 8 2 8 4 10 4 10 2 12 2 12 0 14 0 14 2 16 2 16 0 18 0 18 -2 20 -2 20 -4 22 -4 22 -6 24 -6 24 -4 26 -4 26 -6 28 -6 28 -4 30 -4 30 -2 32 -2 32 -4 34 -4 34 -6 36 -6 36 -8 38 -8 38 -10 40 -10 40 -8 42 -8 42 -10 44 -10 44 -8 46 -8 46 -10 48 -10 48 -12 50 -12 50 -14 52 -1...
output:
44 -9 3 32 2 31 3 30 32 59 31 60 4 33 45 -8 108 55 107 56 42 -9 43 -10 44 -9 3 32 2 31 3 30 32 59 31 60 4 33 45 -8 108 55 107 56 42 -9 43 -10 44 -9 3 32 2 31 3 30 32 59 31 60 4 33 45 -8 108 55 107 56 42 -9 43 -10 44 -9 3 32 2 31 3 30 32 59 31 60 4 33 45 -8 108 55 107 56 42 -9 43 -10 44 -9 3 32 2 31 ...
result:
ok 3000 lines
Test #7:
score: 0
Accepted
time: 119ms
memory: 121308kb
input:
499996 50000 2 0 2 -2 4 -2 4 0 6 0 6 -2 8 -2 8 -4 10 -4 10 -2 12 -2 12 -4 14 -4 14 -6 16 -6 16 -8 18 -8 18 -6 20 -6 20 -4 22 -4 22 -2 24 -2 24 -4 26 -4 26 -2 28 -2 28 -4 30 -4 30 -2 32 -2 32 0 34 0 34 2 36 2 36 4 38 4 38 2 40 2 40 4 42 4 42 6 44 6 44 4 46 4 46 6 48 6 48 8 50 8 50 10 52 10 52 8 54 8 ...
output:
124868 71163 124867 71164 53412 -291 53413 -292 53414 -291 -21 53144 -22 53143 53409 -288 124864 71167 71235 124796 71234 124795 124869 71160 124870 71161 124869 71162 53416 -291 53417 -292 53418 -291 -21 53148 -22 53147 -21 53146 71642 124809 71641 124810 -18 53151 53421 -288 124868 71159 71233 124...
result:
ok 50000 lines
Test #8:
score: 0
Accepted
time: 192ms
memory: 122816kb
input:
499996 500000 2 0 2 -2 4 -2 4 -4 6 -4 6 -2 8 -2 8 -4 10 -4 10 -2 12 -2 12 0 14 0 14 2 16 2 16 4 18 4 18 2 20 2 20 4 22 4 22 2 24 2 24 4 26 4 26 6 28 6 28 8 30 8 30 6 32 6 32 4 34 4 34 2 36 2 36 4 38 4 38 2 40 2 40 4 42 4 42 6 44 6 44 4 46 4 46 2 48 2 48 0 50 0 50 2 52 2 52 0 54 0 54 2 56 2 56 4 58 4...
output:
23678 93 -295 24066 -296 24065 23673 96 80350 56773 -61 137184 -62 137183 80351 56770 80352 56771 80351 56772 23674 95 23675 94 80350 56769 -63 137182 -64 137181 80357 56760 80358 56761 80357 56762 23692 97 23693 96 23694 97 -299 24090 -300 24089 23689 100 80354 56765 80353 56766 23682 95 23683 94 2...
result:
ok 500000 lines
Test #9:
score: 0
Accepted
time: 25ms
memory: 101752kb
input:
82 250 0 0 2 0 2 4 4 4 4 0 26 0 26 10 16 10 16 6 10 6 10 8 14 8 14 12 18 12 18 16 28 16 28 14 20 14 20 12 34 12 34 16 36 16 36 12 44 12 44 6 38 6 38 8 42 8 42 10 28 10 28 0 46 0 46 2 34 2 34 6 32 6 32 2 30 2 30 8 36 8 36 4 46 4 46 18 40 18 40 16 44 16 44 14 38 14 38 18 32 18 32 14 30 14 30 18 4 18 4...
output:
11 10 13 8 14 9 12 11 15 14 17 12 18 13 16 15 19 18 21 16 23 18 25 16 27 18 30 15 27 12 25 14 23 12 21 14 20 13 21 12 23 14 25 12 27 14 29 12 31 14 33 12 34 13 32 15 35 18 38 15 36 13 37 12 39 14 41 12 43 14 46 11 44 9 46 7 43 4 41 6 39 4 36 7 39 10 41 8 42 9 41 10 39 8 37 10 35 8 33 10 31 8 29 10 2...
result:
ok 250 lines
Test #10:
score: 0
Accepted
time: 45ms
memory: 101700kb
input:
216 98765 -78 -32 -64 -32 -64 -24 -44 -24 -44 -20 -38 -20 -38 -30 -60 -30 -60 -32 -28 -32 -28 -24 -26 -24 -26 -32 -16 -32 -16 -20 -14 -20 -14 -32 -8 -32 -8 -20 -4 -20 -4 -32 6 -32 6 -16 20 -16 20 -2 6 -2 6 14 -4 14 -4 8 -10 8 -10 -14 -16 -14 -16 0 -14 0 -14 -4 -12 -4 -12 22 -10 22 -10 10 -8 10 -8 22...
output:
-71 -30 -69 -32 -64 -27 -68 -23 -67 -22 -64 -25 -68 -29 -65 -32 -64 -31 -68 -27 -63 -22 -61 -24 -59 -22 -57 -24 -55 -22 -53 -24 -51 -22 -49 -24 -47 -22 -45 -24 -44 -23 -46 -21 -43 -18 -41 -20 -39 -18 -36 -21 -38 -23 -36 -25 -38 -27 -36 -29 -39 -32 -41 -30 -43 -32 -45 -30 -47 -32 -49 -30 -51 -32 -53 ...
result:
ok 98765 lines
Test #11:
score: 0
Accepted
time: 160ms
memory: 112492kb
input:
174078 500000 0 0 2 0 2 12 4 12 4 0 10 0 10 4 14 4 14 8 16 8 16 2 12 2 12 0 26 0 26 4 38 4 38 8 50 8 50 12 54 12 54 18 44 18 44 14 28 14 28 10 22 10 22 22 14 22 14 28 18 28 18 32 24 32 24 30 20 30 20 26 16 26 16 24 46 24 46 28 50 28 50 32 52 32 52 26 48 26 48 22 40 22 40 18 30 18 30 20 38 20 38 22 2...
output:
497 554 498 553 496 551 499 548 502 551 500 553 502 555 500 557 502 559 499 562 496 559 498 557 497 556 495 558 493 556 492 557 494 559 492 561 494 563 491 566 489 564 487 566 485 564 483 566 481 564 479 566 477 564 476 565 478 567 475 570 473 568 471 570 469 568 468 569 470 571 467 574 465 572 463 ...
result:
ok 500000 lines
Test #12:
score: 0
Accepted
time: 152ms
memory: 113520kb
input:
87166 500000 -990 -1000 -988 -1000 -988 -952 -964 -952 -964 -954 -972 -954 -972 -964 -980 -964 -980 -974 -972 -974 -972 -994 -962 -994 -962 -968 -954 -968 -954 -962 -950 -962 -950 -954 -954 -954 -954 -952 -950 -952 -950 -940 -954 -940 -954 -930 -962 -930 -962 -924 -980 -924 -980 -938 -972 -938 -972 ...
output:
208 -685 205 -682 203 -684 196 -677 203 -670 204 -671 196 -679 201 -684 204 -681 193 -670 189 -674 185 -670 175 -680 171 -676 167 -680 164 -677 166 -675 164 -673 166 -671 164 -669 166 -667 165 -666 163 -668 158 -663 162 -659 158 -655 161 -652 162 -653 158 -657 162 -661 158 -665 161 -668 163 -666 166...
result:
ok 500000 lines
Test #13:
score: 0
Accepted
time: 53ms
memory: 101904kb
input:
4 200000 0 0 3240 0 3240 1428 0 1428 3239 0
output:
3240 1 1813 1428 385 0 0 385 1043 1428 2471 0 3240 769 2581 1428 1153 0 0 1153 275 1428 1703 0 3131 1428 3240 1319 1921 0 493 1428 0 935 935 0 2363 1428 3240 551 2689 0 1261 1428 0 167 167 0 1595 1428 3023 0 3240 217 2029 1428 601 0 0 601 827 1428 2255 0 3240 985 2797 1428 1369 0 0 1369 59 1428 1487...
result:
ok 200000 lines
Test #14:
score: 0
Accepted
time: 146ms
memory: 117228kb
input:
4 500000 0 0 249998 0 249998 250000 0 250000 249997 0
output:
249998 1 0 249999 1 250000 249998 3 249995 0 0 249995 5 250000 249998 7 249991 0 0 249991 9 250000 249998 11 249987 0 0 249987 13 250000 249998 15 249983 0 0 249983 17 250000 249998 19 249979 0 0 249979 21 250000 249998 23 249975 0 0 249975 25 250000 249998 27 249971 0 0 249971 29 250000 249998 31 2...
result:
ok 500000 lines
Test #15:
score: 0
Accepted
time: 221ms
memory: 117360kb
input:
4 500000 0 0 391622 0 391622 108378 0 108378 391621 0
output:
391622 1 283245 108378 174867 0 66489 108378 0 41889 41889 0 150267 108378 258645 0 367023 108378 391622 83779 307843 0 199465 108378 91087 0 0 91087 17291 108378 125669 0 234047 108378 342425 0 391622 49197 332441 108378 224063 0 115685 108378 7307 0 0 7307 101071 108378 209449 0 317827 108378 3916...
result:
ok 500000 lines
Test #16:
score: 0
Accepted
time: 25ms
memory: 101628kb
input:
36 4000 0 0 50 0 50 34 0 34 0 4 46 4 46 30 4 30 4 8 42 8 42 26 8 26 8 12 38 12 38 22 12 22 12 16 34 16 34 18 14 18 14 20 36 20 36 14 10 14 10 24 40 24 40 10 6 10 6 28 44 28 44 6 2 6 2 32 48 32 48 2 0 2 44 27
output:
46 29 45 30 43 28 41 30 39 28 37 30 35 28 33 30 31 28 29 30 27 28 25 30 23 28 21 30 19 28 17 30 15 28 13 30 11 28 9 30 7 28 5 30 4 29 6 27 4 25 6 23 4 21 6 19 4 17 6 15 4 13 6 11 4 9 5 8 7 10 9 8 11 10 13 8 15 10 17 8 19 10 21 8 23 10 25 8 27 10 29 8 31 10 33 8 35 10 37 8 39 10 41 8 42 9 40 11 42 13...
result:
ok 4000 lines
Test #17:
score: 0
Accepted
time: 21ms
memory: 102412kb
input:
32 5000 4 116 6102 116 6102 2116 4 2116 4 448 5202 448 5202 1760 464 1760 464 584 4718 584 4718 1722 564 1722 564 844 4628 844 4628 1540 722 1540 722 1510 4516 1510 4516 1116 662 1116 662 1636 4704 1636 4704 588 484 588 484 1748 4790 1748 4790 470 168 470 168 1818 5708 1818 5708 316 4 316 4077 1510
output:
4107 1540 4137 1510 4167 1540 4197 1510 4227 1540 4257 1510 4287 1540 4317 1510 4347 1540 4377 1510 4407 1540 4437 1510 4467 1540 4497 1510 4527 1540 4628 1439 4516 1327 4628 1215 4257 844 3985 1116 3713 844 3441 1116 3169 844 2897 1116 2625 844 2353 1116 2081 844 1809 1116 1537 844 1265 1116 993 84...
result:
ok 5000 lines
Test #18:
score: 0
Accepted
time: 148ms
memory: 110064kb
input:
500 500000 0 0 3998 0 3998 498 0 498 0 4 3994 4 3994 494 4 494 4 8 3990 8 3990 490 8 490 8 12 3986 12 3986 486 12 486 12 16 3982 16 3982 482 16 482 16 20 3978 20 3978 478 20 478 20 24 3974 24 3974 474 24 474 24 28 3970 28 3970 470 28 470 28 32 3966 32 3966 466 32 466 32 36 3962 36 3962 462 36 462 36...
output:
2259 154 2261 152 2263 154 2265 152 2267 154 2269 152 2271 154 2273 152 2275 154 2277 152 2279 154 2281 152 2283 154 2285 152 2287 154 2289 152 2291 154 2293 152 2295 154 2297 152 2299 154 2301 152 2303 154 2305 152 2307 154 2309 152 2311 154 2313 152 2315 154 2317 152 2319 154 2321 152 2323 154 232...
result:
ok 500000 lines
Test #19:
score: 0
Accepted
time: 131ms
memory: 111384kb
input:
858 500000 2 2 1704 2 1704 2062 2 2062 2 8 1694 8 1694 2052 14 2052 14 14 1674 14 1674 2046 20 2046 20 22 1670 22 1670 2034 32 2034 32 26 1666 26 1666 2026 36 2026 36 32 1654 32 1654 2020 40 2020 40 50 1650 50 1650 2016 50 2016 50 56 1644 56 1644 2006 58 2006 58 62 1638 62 1638 1992 64 1992 64 66 16...
output:
336 1499 334 1501 336 1503 334 1505 336 1507 334 1509 336 1511 334 1513 336 1515 334 1517 336 1519 334 1521 336 1523 334 1525 336 1527 334 1529 336 1531 334 1533 336 1535 334 1537 336 1539 334 1541 336 1543 334 1545 336 1547 334 1549 336 1551 334 1553 336 1555 334 1557 336 1559 334 1561 336 1563 334...
result:
ok 500000 lines
Test #20:
score: 0
Accepted
time: 16ms
memory: 101684kb
input:
66 100 0 0 4 0 4 2 6 2 6 4 8 4 8 6 10 6 10 8 12 8 12 10 14 10 14 12 16 12 16 14 18 14 18 16 20 16 20 18 22 18 22 20 24 20 24 22 26 22 26 24 28 24 28 26 30 26 30 28 32 28 32 30 34 30 34 34 32 34 32 32 30 32 30 30 28 30 28 28 26 28 26 26 24 26 24 24 22 24 22 22 20 22 20 20 18 20 18 18 16 18 16 16 14 1...
output:
34 33 33 34 32 33 34 31 33 30 31 32 30 31 32 29 31 28 29 30 28 29 30 27 29 26 27 28 26 27 28 25 27 24 25 26 24 25 26 23 25 22 23 24 22 23 24 21 23 20 21 22 20 21 22 19 21 18 19 20 18 19 20 17 19 16 17 18 16 17 18 15 17 14 15 16 14 15 16 13 15 12 13 14 12 13 14 11 13 10 11 12 10 11 12 9 11 8 9 10 8 9...
result:
ok 100 lines
Test #21:
score: 0
Accepted
time: 183ms
memory: 120900kb
input:
499998 500000 0 0 4 0 4 2 6 2 6 4 8 4 8 6 10 6 10 8 12 8 12 10 14 10 14 12 16 12 16 14 18 14 18 16 20 16 20 18 22 18 22 20 24 20 24 22 26 22 26 24 28 24 28 26 30 26 30 28 32 28 32 30 34 30 34 32 36 32 36 34 38 34 38 36 40 36 40 38 42 38 42 40 44 40 44 42 46 42 46 44 48 44 48 46 50 46 50 48 52 48 52 ...
output:
250000 249999 249999 250000 249998 249999 250000 249997 249999 249996 249997 249998 249996 249997 249998 249995 249997 249994 249995 249996 249994 249995 249996 249993 249995 249992 249993 249994 249992 249993 249994 249991 249993 249990 249991 249992 249990 249991 249992 249989 249991 249988 249989...
result:
ok 500000 lines