#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)v.size()
const int INF = 1e18;
const int mod = 998244353;
const int N = 1e5+5;
void solve(){
int n; cin >> n;
vector<int> x(n), y(n);
for(int i = 0; i < n; i++){
cin >> x[i] >> y[i];
}
int l = 0, r = 1e9;
int xans = 0;
while(l <= r){
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
int res1 = 0, res2 = 0;
for(int i = 0; i < n; i++){
res1 += abs(m1 - x[i]);
res2 += abs(m2 - x[i]);
}
if(res1 < res2){
r = m2 - 1;
xans = m1;
}else{
l = m1 + 1;
xans = m2;
}
}
l = 0;
r = 1e9;
int yans = 0;
while(l <= r){
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
int res1 = 0, res2 = 0;
for(int i = 0; i < n; i++){
res1 += abs(m1 - y[i]);
res2 += abs(m2 - y[i]);
}
if(res1 < res2){
r = m2 - 1;
yans = m1;
}else{
l = m1 + 1;
yans = m2;
}
}
cout << xans << ' ' << yans;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
}
Compilation message
bestplace.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
65 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
1884 KB |
Output is correct |
2 |
Correct |
23 ms |
2040 KB |
Output is correct |
3 |
Correct |
23 ms |
1884 KB |
Output is correct |
4 |
Correct |
23 ms |
1880 KB |
Output is correct |
5 |
Correct |
23 ms |
2136 KB |
Output is correct |
6 |
Correct |
23 ms |
1884 KB |
Output is correct |
7 |
Correct |
23 ms |
1884 KB |
Output is correct |
8 |
Correct |
22 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
360 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
548 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
1880 KB |
Output is correct |
2 |
Correct |
26 ms |
1884 KB |
Output is correct |
3 |
Correct |
32 ms |
1884 KB |
Output is correct |
4 |
Correct |
24 ms |
1892 KB |
Output is correct |
5 |
Correct |
29 ms |
2012 KB |
Output is correct |
6 |
Correct |
26 ms |
1880 KB |
Output is correct |
7 |
Correct |
27 ms |
1884 KB |
Output is correct |
8 |
Correct |
26 ms |
1880 KB |
Output is correct |