Task: | Retkeily |
Sender: | adex720 |
Submission time: | 2024-01-20 16:37:46 +0200 |
Language: | C++11 |
Status: | READY |
Result: | 50 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | ACCEPTED | 15 |
#3 | ACCEPTED | 25 |
#4 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#2 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#3 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#4 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#5 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#6 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#7 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#8 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#9 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#11 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#12 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#13 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#14 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#15 | ACCEPTED | 0.01 s | 1, 2, 4 | details |
#16 | ACCEPTED | 0.27 s | 2, 4 | details |
#17 | ACCEPTED | 0.23 s | 2, 4 | details |
#18 | ACCEPTED | 0.27 s | 2, 4 | details |
#19 | ACCEPTED | 0.32 s | 2, 3, 4 | details |
#20 | ACCEPTED | 0.28 s | 2, 4 | details |
#21 | ACCEPTED | 0.33 s | 2, 3, 4 | details |
#22 | ACCEPTED | 0.00 s | 1, 3, 4 | details |
#23 | ACCEPTED | 0.01 s | 1, 3, 4 | details |
#24 | ACCEPTED | 0.04 s | 3, 4 | details |
#25 | ACCEPTED | 0.31 s | 3, 4 | details |
#26 | ACCEPTED | 0.35 s | 3, 4 | details |
#27 | ACCEPTED | 0.41 s | 3, 4 | details |
#28 | ACCEPTED | 0.46 s | 3, 4 | details |
#29 | ACCEPTED | 0.00 s | 1, 4 | details |
#30 | ACCEPTED | 0.00 s | 1, 4 | details |
#31 | ACCEPTED | 0.00 s | 1, 4 | details |
#32 | ACCEPTED | 0.00 s | 1, 4 | details |
#33 | ACCEPTED | 0.01 s | 1, 4 | details |
#34 | ACCEPTED | 0.01 s | 1, 4 | details |
#35 | ACCEPTED | 0.00 s | 1, 4 | details |
#36 | ACCEPTED | 0.01 s | 1, 4 | details |
#37 | WRONG ANSWER | 0.07 s | 4 | details |
#38 | WRONG ANSWER | 0.76 s | 4 | details |
#39 | WRONG ANSWER | 0.76 s | 4 | details |
#40 | WRONG ANSWER | 0.76 s | 4 | details |
#41 | WRONG ANSWER | 0.42 s | 4 | details |
Compiler report
input/code.cpp: In function 'void m3(int, int, std::pair<int, int>*, std::pair<int, int>*)': input/code.cpp:106:14: warning: variable 'b' set but not used [-Wunused-but-set-variable] 106 | bool b = false; | ^
Code
#include <bits/stdc++.h> #include <iostream> #include <vector> using namespace std; #define MP make_pair void m1(int n, int m) { pair<int, int> teltat[n]; pair<int, int> paikat[m]; int x, y; for (int i = 0; i < n; i++) { cin >> x >> y; teltat[i] = MP(x, y); } for (int i = 0; i < m; i++) { cin >> x >> y; paikat[i] = MP(x, y); } int suurin = 1; for (int i = 0; i < m; i++) { x = paikat[i].first; y = paikat[i].second; int pienin = INT_MAX; for (int j = 0; j < n; j++) { int etaisyys = abs(x - teltat[j].first) + abs(y - teltat[j].second); if (etaisyys < pienin) { pienin = etaisyys; } } if (pienin > suurin) { suurin = pienin; } } cout << suurin; } bool onTeltta(int x, int y, int n, pair<int, int> teltat[]) { int min = 0; int max = n - 1; while (true) { if (min >= max) { auto teltta = teltat[min]; return teltta.first == x && teltta.second == y; } int keski = (min + max) >> 1; auto teltta = teltat[keski]; if (teltta.first < x) { min = keski + 1; continue; } if (teltta.first > x) { max = keski - 1; continue; } if (teltta.second < y) { min = keski + 1; continue; } if (teltta.second > y) { max = keski - 1; continue; } return true; } } void m3(int n, int m, pair<int, int> teltat[], pair<int, int> paikat[]) { int x, y, x2, y2, y3; int suurin = 1; for (int i = 0; i < m; i++) { x = paikat[i].first; y = paikat[i].second; bool b = false; for (int d = 1; d <= 10; d++) { bool l = false; for (int m = -d; m < d; m++) { x2 = x + m; y2 = y + abs(d - abs(m)); y3 = y - abs(d - abs(m)); if (x2 < 0 || x2 > 1000000) { continue; } if (y2 <= 1000000) { if (onTeltta(x2, y2, n, teltat)) { if (d > suurin) { suurin = d; } l = true; break; } } if (y3 >= 0) { if (onTeltta(x2, y3, n, teltat)) { if (d > suurin) { suurin = d; } l = true; break; } } } if (l) { b = true; break; } } /*if (!b) { cout << "10"; return; }*/ } cout << suurin; } void m2(int n, int m) { pair<int, int> teltat[n]; pair<int, int> paikat[m]; int x, y; int isoin = 1; for (int i = 0; i < n; i++) { cin >> x >> y; x--; y--; teltat[i] = MP(x, y); if (isoin <= 1000) { isoin = max(x, y); } } for (int i = 0; i < m; i++) { cin >> x >> y; x--; y--; paikat[i] = MP(x, y); if (isoin <= 1000) { isoin = max(x, y); } } if (isoin > 1000) { sort(teltat, teltat + n); // ehkä sort(paikat, paikat + m); // ehkä m3(n, m, teltat, paikat); return; } int d[1000000]; bool c[1000000]; priority_queue<pair<int, pair<int, int>>> q; pair<int, int> teltta; for (int i = 0; i < n; i++) { teltta = teltat[i]; x = teltta.first; y = teltta.second; d[x * 1000 + y] = 0; c[x * 1000 + y] = 1; if (x > 0) { if (!c[(x - 1) * 1000 + y]) { q.push(MP(-1, MP(x - 1, y))); c[(x - 1) * 1000 + y] = 1; } } if (x < 999) { if (!c[(x + 1) * 1000 + y]) { q.push(MP(-1, MP(x + 1, y))); c[(x + 1) * 1000 + y] = 1; } } if (y > 0) { if (!c[x * 1000 + y - 1]) { q.push(MP(-1, MP(x, y - 1))); c[x * 1000 + y - 1] = 1; } } if (y < 999) { if (!c[x * 1000 + y + 1]) { q.push(MP(-1, MP(x, y + 1))); c[x * 1000 + y + 1] = 1; } } } int dist; while (!q.empty()) { auto ruutu = q.top(); q.pop(); dist = -ruutu.first; x = ruutu.second.first; y = ruutu.second.second; d[x * 1000 + y] = dist; if (x > 0) { if (!c[(x - 1) * 1000 + y]) { q.push(MP(-dist - 1, MP(x - 1, y))); c[(x - 1) * 1000 + y] = 1; } } if (x < 999) { if (!c[(x + 1) * 1000 + y]) { q.push(MP(-dist - 1, MP(x + 1, y))); c[(x + 1) * 1000 + y] = 1; } } if (y > 0) { if (!c[x * 1000 + y - 1]) { q.push(MP(-dist - 1, MP(x, y - 1))); c[x * 1000 + y - 1] = 1; } } if (y < 999) { if (!c[x * 1000 + y + 1]) { q.push(MP(-dist - 1, MP(x, y + 1))); c[x * 1000 + y + 1] = 1; } } } int suurin = 1; int arvo; for (int i = 0; i < m; i++) { auto paikka = paikat[i]; x = paikka.first; y = paikka.second; arvo = d[x * 1000 + y]; if (arvo > suurin) { suurin = arvo; } } /*for (int x = 0; x < 20; x++) { for (int y = 0; y < 20; y++) { cout << d[x * 1000 + y] << " "; } cout << "\n"; }*/ cout << suurin; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; if (n <= 1000 && m <= 1000) { m1(n, m); return 0; } m2(n, m); }
Test details
Test 1
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
1 1 6 6 8 9 |
correct output |
---|
5 |
user output |
---|
5 |
Test 2
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
5 5 5 10 8 10 1 2 4 10 ... |
correct output |
---|
4 |
user output |
---|
4 |
Test 3
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
10 10 5 2 1 10 6 10 5 5 ... |
correct output |
---|
5 |
user output |
---|
5 |
Test 4
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
10 5 6 1 8 9 3 2 6 6 ... |
correct output |
---|
3 |
user output |
---|
3 |
Test 5
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
5 10 10 10 6 2 10 9 8 7 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 6
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1 1 55 68 28 42 |
correct output |
---|
53 |
user output |
---|
53 |
Test 7
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 100 52 56 58 96 3 99 18 1 ... |
correct output |
---|
20 |
user output |
---|
20 |
Test 8
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
1000 100 60 40 68 47 30 32 74 52 ... |
correct output |
---|
5 |
user output |
---|
5 |
Test 9
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 1000 44 26 18 81 18 6 83 90 ... |
correct output |
---|
20 |
user output |
---|
20 |
Test 10
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
1000 1000 15 13 23 79 81 43 30 40 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 11
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1 1 948 495 227 149 |
correct output |
---|
1067 |
user output |
---|
1067 |
Test 12
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 100 114 530 748 841 612 709 810 232 ... |
correct output |
---|
203 |
user output |
---|
203 |
Test 13
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1000 100 225 82 265 691 978 367 993 396 ... |
correct output |
---|
50 |
user output |
---|
50 |
Test 14
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 1000 848 668 189 716 451 80 626 973 ... |
correct output |
---|
192 |
user output |
---|
192 |
Test 15
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1000 1000 931 656 382 809 666 609 1000 923 ... |
correct output |
---|
66 |
user output |
---|
66 |
Test 16
Group: 2, 4
Verdict: ACCEPTED
input |
---|
10000 1000 961 158 561 313 991 125 821 964 ... |
correct output |
---|
18 |
user output |
---|
18 |
Test 17
Group: 2, 4
Verdict: ACCEPTED
input |
---|
1000 10000 428 1000 485 958 46 915 582 127 ... |
correct output |
---|
67 |
user output |
---|
67 |
Test 18
Group: 2, 4
Verdict: ACCEPTED
input |
---|
10000 10000 503 849 367 829 448 926 362 512 ... |
correct output |
---|
22 |
user output |
---|
22 |
Test 19
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
100000 10000 111 705 808 24 69 858 961 122 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 20
Group: 2, 4
Verdict: ACCEPTED
input |
---|
10000 100000 844 874 339 315 819 918 627 936 ... |
correct output |
---|
27 |
user output |
---|
27 |
Test 21
Group: 2, 3, 4
Verdict: ACCEPTED
input |
---|
100000 100000 100 468 303 899 784 458 505 54 ... |
correct output |
---|
8 |
user output |
---|
8 |
Test 22
Group: 1, 3, 4
Verdict: ACCEPTED
input |
---|
10 10 451219 220496 369161 161920 241139 700531 811276 993633 ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 23
Group: 1, 3, 4
Verdict: ACCEPTED
input |
---|
1000 1000 337358 113599 674585 852084 717817 983395 895431 391144 ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 24
Group: 3, 4
Verdict: ACCEPTED
input |
---|
10000 10000 636432 664736 341727 37864 469264 360610 545785 879043 ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 25
Group: 3, 4
Verdict: ACCEPTED
input |
---|
100000 100000 750315 55215 550921 465416 435380 742666 288479 495099 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 26
Group: 3, 4
Verdict: ACCEPTED
input |
---|
100000 100000 416825 677767 347155 162523 602643 936386 181956 517732 ... |
correct output |
---|
8 |
user output |
---|
8 |
Test 27
Group: 3, 4
Verdict: ACCEPTED
input |
---|
100000 100000 155202 457283 421100 55104 604625 136495 841749 569346 ... |
correct output |
---|
9 |
user output |
---|
9 |
Test 28
Group: 3, 4
Verdict: ACCEPTED
input |
---|
100000 100000 290146 808578 489810 268578 956361 635214 939844 534435 ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 29
Group: 1, 4
Verdict: ACCEPTED
input |
---|
10 10 668880 791821 226050 188133 859493 736633 290460 838926 ... |
correct output |
---|
342068 |
user output |
---|
342068 |
Test 30
Group: 1, 4
Verdict: ACCEPTED
input |
---|
100 100 729367 697755 338457 742774 535371 701216 93743 555995 ... |
correct output |
---|
285526 |
user output |
---|
285526 |
Test 31
Group: 1, 4
Verdict: ACCEPTED
input |
---|
100 1000 50870 539657 476809 462765 311713 355546 901838 829393 ... |
correct output |
---|
255789 |
user output |
---|
255789 |
Test 32
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 100 182415 659794 581623 510256 594984 525993 367726 938015 ... |
correct output |
---|
50501 |
user output |
---|
50501 |
Test 33
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 1000 668976 422918 350791 933024 893307 88057 278098 13847 ... |
correct output |
---|
57897 |
user output |
---|
57897 |
Test 34
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 1000 701742 116334 278337 368995 187245 133297 273083 369187 ... |
correct output |
---|
60537 |
user output |
---|
60537 |
Test 35
Group: 1, 4
Verdict: ACCEPTED
input |
---|
10 10 693836 74759 61731 520849 666762 45364 559335 979511 ... |
correct output |
---|
417182 |
user output |
---|
417182 |
Test 36
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 1000 207572 43521 513003 683552 58800 253576 16541 558695 ... |
correct output |
---|
69609 |
user output |
---|
69609 |
Test 37
Group: 4
Verdict: WRONG ANSWER
input |
---|
10000 10000 89066 605574 504488 66068 959128 348414 68004 849599 ... |
correct output |
---|
22936 |
user output |
---|
1 |
Test 38
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 100000 20824 214259 463783 904059 603615 769692 789080 399093 ... |
correct output |
---|
8070 |
user output |
---|
7 |
Test 39
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 100000 811424 464350 336948 946495 204883 914446 171888 431769 ... |
correct output |
---|
8240 |
user output |
---|
7 |
Test 40
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 100000 850810 902354 292608 63461 223139 188900 197760 995048 ... |
correct output |
---|
7769 |
user output |
---|
1 |
Test 41
Group: 4
Verdict: WRONG ANSWER
input |
---|
100000 100000 1 1 1 2 1 3 1 4 ... |
correct output |
---|
1899999 |
user output |
---|
1 |