#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#define ll long long int
#define pb push_back
#define pll pair < ll , ll >
#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
ll inf2 = 3e18;
ll x[ 100111 ], y[ 100111 ], used[ 3 ][ 100111 ], ans;
vector < pll > unused, overused;
int main(){
ll n;
cin >> n;
for(int i = 1; i <= n * 2; i ++){
cin >> x[ i ] >> y[ i ];
}
for(int i = 1; i <= n * 2; i ++){
if(1 <= x[ i ] && x[ i ] <= n && 1 <= y[ i ] && y[ i ] <= 2){
used[ y[ i ] ][ x[ i ] ] ++;
// cout << "Selam\n";
}else if(1 <= x[ i ] && x[ i ] <= n){
if(y[ i ] < 1){
ans += abs(1 - y[ i ]);
used[ 1 ][ x[ i ] ] ++;
// cout << "1: " << ans << " i:" << i << "\n";
}else{
ans += abs(2 - y[ i ]);
used[ 2 ][ x[ i ] ] ++;
// cout << "2: " << ans << " i:" << i << "\n";
}
}else if(1 <= y[ i ] && y[ i ] <= 2){
if(x[ i ] < 1){
ans += abs(1 - x[ i ]);
used[ y[ i ] ][ 1 ] ++;
// cout << "3: " << ans << " i:" << i << "\n";
}else{
ans += abs(n - x[ i ]);
used[ y[ i ] ][ n ] ++;
// cout << "4: " << ans << " i:" << i << "\n";
}
}else{
ll lt, rt, lb, rb, mn;
lt = abs(x[ i ] - 1) + abs(y[ i ] - 2);
lb = abs(x[ i ] - 1) + abs(y[ i ] - 1);
rt = abs(x[ i ] - n) + abs(y[ i ] - 2);
rb = abs(x[ i ] - n) + abs(y[ i ] - 1);
mn = min(min(lt, lb), min(rb, rt));
ans += mn;
if(mn == lt){
used[ 2 ][ 1 ] ++;
}else if(mn == lb){
used[ 1 ][ 1 ] ++;
}else if(mn == rt){
used[ 2 ][ n ] ++;
}else{
used[ 1 ][ n ] ++;
}
// cout << "5: " << ans << " i:" << i << "\n";
}
}
for(int i = 1; i <= 2; i ++){
for(int j = 1; j <= n; j ++){
if(!used[ i ][ j ]){
unused.pb(make_pair(i, j));
}
if(used[ i ][ j ] > 1){
for(int k = 2; k <= used[ i ][ j ]; k ++)
overused.pb(make_pair(i, j));
}
}
}
for(int i = 0; i < overused.size(); i ++){
ll mn = inf2, id = -1;
for(int j = 0; j < unused.size(); j ++){
ll manhut_dis = abs(overused[ i ].fi - unused[ j ].fi) + abs(overused[ i ].se - unused[ j ].se);
if(manhut_dis < mn){
mn = manhut_dis;
id = j;
}
}
ans += mn;
unused.erase(unused.begin() + id);
}
// for(int i = 1; i <= 2; i ++){
// for(int j = 1; j <= n; j ++){
// cout << used[ i ][ j ] << " ";
// }
// cout << "\n";
// }
cout << "\n" << ans;
}
/*
4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1
3
0 0
0 4
4 0
2 1
2 5
-1 1
5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3
*/
Compilation message
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < overused.size(); i ++){
| ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int j = 0; j < unused.size(); j ++){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
280 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
280 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
280 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
