using namespace std;
#include <iostream>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
int N,qx[MAXN],qy[MAXN];
map<pair<int,int>,pair<pair<int,int>,int>> edges;
set<pair<int,int>> s;
pair<int,int> LCA(pair<int,int> p1,pair<int,int> p2) {
vector<pair<int,int>> v1,v2;
v1.push_back(p1);
while(p1.first != 0 || p1.second != 0) {
for(int i = 0;i <= 31;++i) {
int cur = 1 << i;
if(p1.first % cur != 0) {
p1.first -= cur >> 1;
v1.push_back(p1);
}else if(p1.second % cur != 0) {
p1.second -= cur >> 1;
v1.push_back(p1);
}
}
}
v2.push_back(p2);
while(p2.first != 0 || p2.second != 0) {
for(int i = 0;i <= 31;++i) {
int cur = 1 << i;
if(p2.first % cur != 0) {
p2.first -= cur >> 1;
v2.push_back(p2);
}else if(p2.second % cur != 0) {
p2.second -= cur >> 1;
v2.push_back(p2);
}
}
}
// for(int i = 0;i < v1.size();++i) {
// cout << v1[i].first << " " << v1[i].second << endl;
// }
// cout << endl;
// for(int i = 0;i < v2.size();++i) {
// cout << v2[i].first << " " << v2[i].second << endl;
// }
int where = -1;
for(int i = min(v1.size() - 1,v2.size() - 1);i >= 0;--i) {
// cout << v1[i].first << " " << v1[i].second << " " << v2[i].first << " " << v2[i].second << endl;
if(v1[v1.size() - 1 - i] == v2[v2.size() - 1 - i]) {
where = i;
break;
}
}
if(where == -1) {
return {0,0};
}
if(where != min(v1.size() - 1,v2.size() - 1)) where++;
return {min(v1[v1.size() - 1 - where].first,v2[v2.size() - 1 - where].first),min(v1[v1.size() - 1 - where].second,v2[v2.size() - 1 - where].second)};
}
int main() {
cin >> N;
for(int i = 0;i < N;++i) {
cin >> qx[i] >> qy[i];
}
for(int i = 0;i < N;++i) {
for(int j = i;j < N;++j) {
s.insert(LCA({qx[i],qy[i]},{qx[j],qy[j]}));
}
}
long long ans = 1e15;
for(auto itr = s.begin();itr != s.end();++itr) {
long long curN = 0;
for(int i = 0;i < N;++i) {
pair<int,int> cur = LCA(*itr,{qx[i],qy[i]});
curN += abs(cur.first - qx[i]) + abs(cur.second - qy[i]) + abs(cur.first - itr -> first) + abs(cur.second - itr -> second);
}
ans = min(ans,curN);
}
cout << ans << endl;
return 0;
}
Compilation message
cvenk.cpp: In function 'std::pair<int, int> LCA(std::pair<int, int>, std::pair<int, int>)':
cvenk.cpp:60:11: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
60 | if(where != min(v1.size() - 1,v2.size() - 1)) where++;
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
2060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3070 ms |
3052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
