Task: | Manhattan sightseeing |
Sender: | aalto2024f_002 |
Submission time: | 2024-10-02 17:48:56 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | ACCEPTED | 0.00 s | details |
#19 | ACCEPTED | 0.00 s | details |
#20 | ACCEPTED | 0.00 s | details |
#21 | ACCEPTED | 0.00 s | details |
#22 | ACCEPTED | 0.00 s | details |
#23 | ACCEPTED | 0.00 s | details |
#24 | ACCEPTED | 0.00 s | details |
#25 | ACCEPTED | 0.00 s | details |
#26 | ACCEPTED | 0.00 s | details |
#27 | ACCEPTED | 0.00 s | details |
#28 | ACCEPTED | 0.00 s | details |
#29 | ACCEPTED | 0.00 s | details |
#30 | ACCEPTED | 0.00 s | details |
#31 | ACCEPTED | 0.00 s | details |
#32 | ACCEPTED | 0.00 s | details |
#33 | ACCEPTED | 0.00 s | details |
#34 | ACCEPTED | 0.00 s | details |
#35 | ACCEPTED | 0.00 s | details |
#36 | ACCEPTED | 0.00 s | details |
#37 | ACCEPTED | 0.00 s | details |
#38 | ACCEPTED | 0.00 s | details |
#39 | ACCEPTED | 0.00 s | details |
#40 | ACCEPTED | 0.00 s | details |
#41 | ACCEPTED | 0.00 s | details |
#42 | ACCEPTED | 0.00 s | details |
#43 | ACCEPTED | 0.00 s | details |
#44 | ACCEPTED | 0.00 s | details |
#45 | ACCEPTED | 0.00 s | details |
#46 | ACCEPTED | 0.00 s | details |
#47 | ACCEPTED | 0.00 s | details |
#48 | ACCEPTED | 0.00 s | details |
#49 | ACCEPTED | 0.00 s | details |
#50 | ACCEPTED | 0.00 s | details |
#51 | ACCEPTED | 0.00 s | details |
#52 | ACCEPTED | 0.00 s | details |
#53 | ACCEPTED | 0.00 s | details |
#54 | ACCEPTED | 0.00 s | details |
#55 | ACCEPTED | 0.00 s | details |
#56 | ACCEPTED | 0.00 s | details |
#57 | ACCEPTED | 0.00 s | details |
#58 | ACCEPTED | 0.00 s | details |
#59 | ACCEPTED | 0.00 s | details |
#60 | ACCEPTED | 0.00 s | details |
#61 | ACCEPTED | 0.00 s | details |
#62 | ACCEPTED | 0.00 s | details |
#63 | ACCEPTED | 0.00 s | details |
#64 | ACCEPTED | 0.00 s | details |
#65 | ACCEPTED | 0.00 s | details |
#66 | ACCEPTED | 0.00 s | details |
#67 | ACCEPTED | 0.00 s | details |
#68 | ACCEPTED | 0.06 s | details |
#69 | ACCEPTED | 0.06 s | details |
#70 | ACCEPTED | 0.06 s | details |
#71 | ACCEPTED | 0.06 s | details |
#72 | ACCEPTED | 0.06 s | details |
#73 | ACCEPTED | 0.06 s | details |
#74 | ACCEPTED | 0.06 s | details |
#75 | ACCEPTED | 0.06 s | details |
#76 | ACCEPTED | 0.06 s | details |
#77 | ACCEPTED | 0.06 s | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:90:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses] 90 | int mid = low + high >> 1; | ~~~~^~~~~~
Code
#include <algorithm> #include <bits/stdc++.h> #include <string> using namespace std; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define int long long string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif const int N = 1e5 + 5; const int INF = 3e9; int n, x[N], y[N], orix[N], oriy[N]; bool check(int d) { int mxx = -INF, mnx = INF, mxy = -INF, mny = INF; for (int i = 1; i <= n; i++) { mxx = max(mxx, x[i] - d); mxy = max(mxy, y[i] - d); mnx = min(mnx, x[i] + d); mny = min(mny, y[i] + d); } return mxx <= mnx && mxy <= mny; } void solve() { cin >> n; // int mxx = 0, mnx = INF, mxy = 0, mny = INF; for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i]; int xx = x[i], yy = y[i]; orix[i] = xx, oriy[i] = yy; x[i] = xx - yy; y[i] = xx + yy; // mxx = max(mxx, x[i]); // mxy = max(mxy, y[i]); // mnx = min(mnx, x[i]); // mny = min(mny, y[i]); } int low = -INF, high = INF, ans = -1; while (low <= high) { int mid = low + high >> 1; if (check(mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } // cout << ans << '\n'; int mxx = -INF, mnx = INF, mxy = -INF, mny = INF; for (int i = 1; i <= n; i++) { mxx = max(mxx, x[i] - ans); mxy = max(mxy, y[i] - ans); mnx = min(mnx, x[i] + ans); mny = min(mny, y[i] + ans); } int cx = (mxx + mxy) / 2; int cy = (mxy - mxx) / 2; auto mxdist = [&](int posx, int posy) -> int { int ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, abs(posx - orix[i]) + abs(posy - oriy[i])); } return ans; }; int best = mxdist(cx, cy), ansx = cx, ansy = cy; for (int xx = cx - 5; xx <= cx + 5; xx++) { for (int yy = cy - 5; yy <= cy + 5; yy++) { int cur = mxdist(xx, yy); if (cur < best) { best = cur; ansx = xx; ansy = yy; } } } cout << ansx << ' ' << ansy << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while (t--) { solve(); } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
1 7 7 |
correct output |
---|
7 7 |
user output |
---|
7 7 |
Test 2
Verdict: ACCEPTED
input |
---|
1 1 5 |
correct output |
---|
1 5 |
user output |
---|
1 5 |
Test 3
Verdict: ACCEPTED
input |
---|
2 8 1 3 3 |
correct output |
---|
5 2 |
user output |
---|
4 1 |
Test 4
Verdict: ACCEPTED
input |
---|
2 1 5 3 2 |
correct output |
---|
2 3 |
user output |
---|
1 2 |
Test 5
Verdict: ACCEPTED
input |
---|
3 6 3 2 3 6 1 |
correct output |
---|
4 2 |
user output |
---|
4 2 |
Test 6
Verdict: ACCEPTED
input |
---|
3 9 6 3 8 9 4 |
correct output |
---|
6 6 |
user output |
---|
5 5 |
Test 7
Verdict: ACCEPTED
input |
---|
3 8 7 8 6 8 7 |
correct output |
---|
8 6 |
user output |
---|
8 6 |
Test 8
Verdict: ACCEPTED
input |
---|
4 3 6 9 9 7 9 5 1 |
correct output |
---|
6 6 |
user output |
---|
5 7 |
Test 9
Verdict: ACCEPTED
input |
---|
4 3 1 2 9 8 9 6 8 |
correct output |
---|
4 6 |
user output |
---|
3 7 |
Test 10
Verdict: ACCEPTED
input |
---|
4 6 5 8 3 9 3 7 9 |
correct output |
---|
7 5 |
user output |
---|
7 5 |
Test 11
Verdict: ACCEPTED
input |
---|
4 2 8 9 7 5 1 3 7 |
correct output |
---|
5 6 |
user output |
---|
5 6 |
Test 12
Verdict: ACCEPTED
input |
---|
4 5 5 6 3 8 5 2 4 |
correct output |
---|
4 5 |
user output |
---|
4 5 |
Test 13
Verdict: ACCEPTED
input |
---|
4 7 3 8 7 3 2 8 6 |
correct output |
---|
6 4 |
user output |
---|
5 5 |
Test 14
Verdict: ACCEPTED
input |
---|
4 1 3 7 6 2 6 3 4 |
correct output |
---|
3 5 |
user output |
---|
2 6 |
Test 15
Verdict: ACCEPTED
input |
---|
4 7 8 3 1 2 3 3 2 |
correct output |
---|
4 5 |
user output |
---|
3 6 |
Test 16
Verdict: ACCEPTED
input |
---|
4 2 7 9 1 3 5 2 1 |
correct output |
---|
3 2 |
user output |
---|
2 1 |
Test 17
Verdict: ACCEPTED
input |
---|
4 7 7 2 2 7 3 1 8 |
correct output |
---|
4 5 |
user output |
---|
3 5 |
Test 18
Verdict: ACCEPTED
input |
---|
5 5 6 7 8 6 8 5 8 ... |
correct output |
---|
5 7 |
user output |
---|
4 8 |
Test 19
Verdict: ACCEPTED
input |
---|
5 4 9 7 9 1 2 3 9 ... |
correct output |
---|
3 6 |
user output |
---|
1 8 |
Test 20
Verdict: ACCEPTED
input |
---|
5 4 2 1 9 5 9 4 5 ... |
correct output |
---|
3 6 |
user output |
---|
3 6 |
Test 21
Verdict: ACCEPTED
input |
---|
5 5 1 7 8 3 2 5 6 ... |
correct output |
---|
6 4 |
user output |
---|
5 5 |
Test 22
Verdict: ACCEPTED
input |
---|
5 9 9 5 2 9 8 7 6 ... |
correct output |
---|
6 6 |
user output |
---|
5 7 |
Test 23
Verdict: ACCEPTED
input |
---|
5 2 1 8 8 2 4 9 9 ... |
correct output |
---|
5 5 |
user output |
---|
3 7 |
Test 24
Verdict: ACCEPTED
input |
---|
5 9 9 3 2 8 1 1 4 ... |
correct output |
---|
5 5 |
user output |
---|
5 5 |
Test 25
Verdict: ACCEPTED
input |
---|
5 1 3 8 3 4 9 7 5 ... |
correct output |
---|
4 4 |
user output |
---|
4 3 |
Test 26
Verdict: ACCEPTED
input |
---|
5 8 1 9 3 8 4 5 8 ... |
correct output |
---|
6 4 |
user output |
---|
5 3 |
Test 27
Verdict: ACCEPTED
input |
---|
5 1 4 5 5 5 1 2 3 ... |
correct output |
---|
3 3 |
user output |
---|
3 3 |
Test 28
Verdict: ACCEPTED
input |
---|
10 5 6 7 8 6 8 5 8 ... |
correct output |
---|
6 4 |
user output |
---|
6 3 |
Test 29
Verdict: ACCEPTED
input |
---|
10 4 9 7 9 1 2 3 9 ... |
correct output |
---|
3 6 |
user output |
---|
1 8 |
Test 30
Verdict: ACCEPTED
input |
---|
10 4 2 1 9 5 9 4 5 ... |
correct output |
---|
3 5 |
user output |
---|
3 5 |
Test 31
Verdict: ACCEPTED
input |
---|
10 5 1 7 8 3 2 5 6 ... |
correct output |
---|
5 3 |
user output |
---|
5 3 |
Test 32
Verdict: ACCEPTED
input |
---|
10 9 9 5 2 9 8 7 6 ... |
correct output |
---|
5 6 |
user output |
---|
5 6 |
Test 33
Verdict: ACCEPTED
input |
---|
10 2 1 8 8 2 4 9 9 ... |
correct output |
---|
4 6 |
user output |
---|
3 7 |
Test 34
Verdict: ACCEPTED
input |
---|
10 9 9 3 2 8 1 1 4 ... |
correct output |
---|
5 5 |
user output |
---|
5 5 |
Test 35
Verdict: ACCEPTED
input |
---|
10 1 3 8 3 4 9 7 5 ... |
correct output |
---|
4 4 |
user output |
---|
4 3 |
Test 36
Verdict: ACCEPTED
input |
---|
10 8 1 9 3 8 4 5 8 ... |
correct output |
---|
5 4 |
user output |
---|
5 4 |
Test 37
Verdict: ACCEPTED
input |
---|
10 1 4 5 5 5 1 2 3 ... |
correct output |
---|
2 3 |
user output |
---|
2 3 |
Test 38
Verdict: ACCEPTED
input |
---|
100 589284012 636562060 767928734 906523441 647212241 921212095 585063857 909729626 ... |
correct output |
---|
485094485 480883850 |
user output |
---|
480089022 485889313 |
Test 39
Verdict: ACCEPTED
input |
---|
100 447773962 773442532 122816 137572579 324627123 157577940 253498609 99147813 ... |
correct output |
---|
534004334 480422569 |
user output |
---|
522194257 492232646 |
Test 40
Verdict: ACCEPTED
input |
---|
100 468145963 198730372 27838076 590195590 467423861 520495379 451366491 344173378 ... |
correct output |
---|
505241702 553085427 |
user output |
---|
503265085 551108811 |
Test 41
Verdict: ACCEPTED
input |
---|
100 591414747 75940263 760367935 901888417 312356591 130275571 548496961 611293382 ... |
correct output |
---|
512794087 502710728 |
user output |
---|
476603423 466520064 |
Test 42
Verdict: ACCEPTED
input |
---|
100 967034924 587586158 185430194 918715995 767527830 653946995 749180621 641621091 ... |
correct output |
---|
467598795 543711879 |
user output |
---|
401134936 610175738 |
Test 43
Verdict: ACCEPTED
input |
---|
100 238363353 59249204 934941692 892631472 221963002 390559518 986350949 524427523 ... |
correct output |
---|
511067632 465512739 |
user output |
---|
509349069 467231302 |
Test 44
Verdict: ACCEPTED
input |
---|
100 958701283 356460601 224848374 881788059 68992860 44771412 397401947 115595477 ... |
correct output |
---|
542243492 445601576 |
user output |
---|
531567647 434925731 |
Test 45
Verdict: ACCEPTED
input |
---|
100 81935404 244103474 837431431 342493822 470738321 776814822 489180570 330726191 ... |
correct output |
---|
530569655 531085018 |
user output |
---|
522927503 523442866 |
Test 46
Verdict: ACCEPTED
input |
---|
100 937837681 11934038 257096283 933290530 405355767 570001955 876668629 249890139 ... |
correct output |
---|
489890640 449453691 |
user output |
---|
481961188 441524238 |
Test 47
Verdict: ACCEPTED
input |
---|
100 11139168 391337048 538883744 535937150 532332526 8099343 143698367 339543270 ... |
correct output |
---|
478577648 507747978 |
user output |
---|
445518840 540806786 |
Test 48
Verdict: ACCEPTED
input |
---|
200 589284012 636562060 767928734 906523441 647212241 921212095 585063857 909729626 ... |
correct output |
---|
484364945 481613390 |
user output |
---|
480089022 485889313 |
Test 49
Verdict: ACCEPTED
input |
---|
200 447773962 773442532 122816 137572579 324627123 157577940 253498609 99147813 ... |
correct output |
---|
528519875 485907028 |
user output |
---|
524367329 490059574 |
Test 50
Verdict: ACCEPTED
input |
---|
200 468145963 198730372 27838076 590195590 467423861 520495379 451366491 344173378 ... |
correct output |
---|
482800416 512251704 |
user output |
---|
416974595 578077525 |
Test 51
Verdict: ACCEPTED
input |
---|
200 591414747 75940263 760367935 901888417 312356591 130275571 548496961 611293382 ... |
correct output |
---|
492010316 481926957 |
user output |
---|
476603423 466520064 |
Test 52
Verdict: ACCEPTED
input |
---|
200 967034924 587586158 185430194 918715995 767527830 653946995 749180621 641621091 ... |
correct output |
---|
473998199 537312475 |
user output |
---|
435602069 575708605 |
Test 53
Verdict: ACCEPTED
input |
---|
200 238363353 59249204 934941692 892631472 221963002 390559518 986350949 524427523 ... |
correct output |
---|
535342378 489787485 |
user output |
---|
509349068 515780795 |
Test 54
Verdict: ACCEPTED
input |
---|
200 958701283 356460601 224848374 881788059 68992860 44771412 397401947 115595477 ... |
correct output |
---|
541418009 466378372 |
user output |
---|
539287866 468508515 |
Test 55
Verdict: ACCEPTED
input |
---|
200 81935404 244103474 837431431 342493822 470738321 776814822 489180570 330726191 ... |
correct output |
---|
471167122 531480104 |
user output |
---|
433362030 569285196 |
Test 56
Verdict: ACCEPTED
input |
---|
200 937837681 11934038 257096283 933290530 405355767 570001955 876668629 249890139 ... |
correct output |
---|
480355638 503030740 |
user output |
---|
462891182 485566284 |
Test 57
Verdict: ACCEPTED
input |
---|
200 11139168 391337048 538883744 535937150 532332526 8099343 143698367 339543270 ... |
correct output |
---|
488427758 499286474 |
user output |
---|
469096007 479954723 |
Test 58
Verdict: ACCEPTED
input |
---|
1000 589284012 636562060 767928734 906523441 647212241 921212095 585063857 909729626 ... |
correct output |
---|
497956378 486069415 |
user output |
---|
485261724 473374760 |
Test 59
Verdict: ACCEPTED
input |
---|
1000 447773962 773442532 122816 137572579 324627123 157577940 253498609 99147813 ... |
correct output |
---|
494047134 512602597 |
user output |
---|
484147914 502703377 |
Test 60
Verdict: ACCEPTED
input |
---|
1000 468145963 198730372 27838076 590195590 467423861 520495379 451366491 344173378 ... |
correct output |
---|
497994845 501561827 |
user output |
---|
478988976 520567696 |
Test 61
Verdict: ACCEPTED
input |
---|
1000 591414747 75940263 760367935 901888417 312356591 130275571 548496961 611293382 ... |
correct output |
---|
483630640 485770068 |
user output |
---|
470614713 472754142 |
Test 62
Verdict: ACCEPTED
input |
---|
1000 967034924 587586158 185430194 918715995 767527830 653946995 749180621 641621091 ... |
correct output |
---|
484246063 524460613 |
user output |
---|
472706010 536000666 |
Test 63
Verdict: ACCEPTED
input |
---|
1000 238363353 59249204 934941692 892631472 221963002 390559518 986350949 524427523 ... |
correct output |
---|
482084242 498558858 |
user output |
---|
458903661 521739439 |
Test 64
Verdict: ACCEPTED
input |
---|
1000 958701283 356460601 224848374 881788059 68992860 44771412 397401947 115595477 ... |
correct output |
---|
517911118 490640905 |
user output |
---|
509266842 481996629 |
Test 65
Verdict: ACCEPTED
input |
---|
1000 81935404 244103474 837431431 342493822 470738321 776814822 489180570 330726191 ... |
correct output |
---|
516584474 493117116 |
user output |
---|
509986438 486519080 |
Test 66
Verdict: ACCEPTED
input |
---|
1000 937837681 11934038 257096283 933290530 405355767 570001955 876668629 249890139 ... |
correct output |
---|
505395058 493501350 |
user output |
---|
492504101 480610392 |
Test 67
Verdict: ACCEPTED
input |
---|
1000 11139168 391337048 538883744 535937150 532332526 8099343 143698367 339543270 ... |
correct output |
---|
487882612 490398120 |
user output |
---|
481494051 484009560 |
Test 68
Verdict: ACCEPTED
input |
---|
100000 589284012 636562060 767928734 906523441 647212241 921212095 585063857 909729626 ... |
correct output |
---|
499279419 501141977 |
user output |
---|
497633629 499496187 |
Test 69
Verdict: ACCEPTED
input |
---|
100000 447773962 773442532 122816 137572579 324627123 157577940 253498609 99147813 ... |
correct output |
---|
499924856 502172257 |
user output |
---|
498603718 500851120 |
Test 70
Verdict: ACCEPTED
input |
---|
100000 468145963 198730372 27838076 590195590 467423861 520495379 451366491 344173378 ... |
correct output |
---|
501207411 500741195 |
user output |
---|
501123514 500657298 |
Test 71
Verdict: ACCEPTED
input |
---|
100000 591414747 75940263 760367935 901888417 312356591 130275571 548496961 611293382 ... |
correct output |
---|
500378568 501125669 |
user output |
---|
500299739 501046840 |
Test 72
Verdict: ACCEPTED
input |
---|
100000 967034924 587586158 185430194 918715995 767527830 653946995 749180621 641621091 ... |
correct output |
---|
501286586 498468528 |
user output |
---|
500463145 499291969 |
Test 73
Verdict: ACCEPTED
input |
---|
100000 238363353 59249204 934941692 892631472 221963002 390559518 986350949 524427523 ... |
correct output |
---|
500851969 501496653 |
user output |
---|
500445206 501089890 |
Test 74
Verdict: ACCEPTED
input |
---|
100000 958701283 356460601 224848374 881788059 68992860 44771412 397401947 115595477 ... |
correct output |
---|
501129059 499760141 |
user output |
---|
501089513 499720595 |
Test 75
Verdict: ACCEPTED
input |
---|
100000 81935404 244103474 837431431 342493822 470738321 776814822 489180570 330726191 ... |
correct output |
---|
501369501 501175764 |
user output |
---|
501136780 501408485 |
Test 76
Verdict: ACCEPTED
input |
---|
100000 937837681 11934038 257096283 933290530 405355767 570001955 876668629 249890139 ... |
correct output |
---|
499822684 498958448 |
user output |
---|
499576138 499204994 |
Test 77
Verdict: ACCEPTED
input |
---|
100000 11139168 391337048 538883744 535937150 532332526 8099343 143698367 339543270 ... |
correct output |
---|
500231553 501043880 |
user output |
---|
498833952 499646279 |