#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
random_device rd;
mt19937 mt(rd());
int32_t main(){
fast
int n;
cin >> n;
int N = n * 2;
int ans = 0;
vector <vector<int> > grid(n + 1, vector<int>(3));
vector <pair<int, int> > p;
for(int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
p.push_back({a, b});
}
shuffle(p.begin(), p.end(), mt);
for(int i = 0; i < N; i++) {
int a = p[i].first, b = p[i].second;
int ydif = min(abs(b - 2), abs(b - 1));
int xdif = min(abs(a - n), abs(a - 1));
if(a >= 1 and a <= n) xdif = 0;
ans += xdif + ydif;
// cout << xdif << " " << ydif << "\n";
int x, y;
x = a + xdif;
if(x < 1 or x > n) x = a - xdif;
y = b + ydif;
if(y < 1 or y > 2) y = b - ydif;
grid[x][y]++;
}
// cout << ans << "\n";
vector <pair<int,int> > point;
array<vector<pair<int,int> >, 2> np;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 2; j++) {
// cout << grid[i][j] << " ";
while(--grid[i][j] > 0) point.push_back({i, j});
}
// cout << "\n";
}
// cout << "\n";
// ilk başta sadece i'lerini önemseyeceğiz
int l = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 2; j++) {
if(!grid[i][j]) continue;
ans += abs(i - point[l].first);
if(point[l].second != j) {
np[j-1].push_back({i, point[l].first});
}
// her bir eşleştirilen ikiliyi çıktı ver
// cout << i << "," << j << " " << point[l].first << "," << point[l].second << "\n";
l++;
}
}
// cout << "\n";
for(auto &it:np[0]) {
if(it.first > it.second) swap(it.first, it.second);
// cout << it.first << " " << it.second << "\n";
}
// cout << "\n";
for(auto &it:np[1]) {
if(it.first > it.second) swap(it.first, it.second);
// cout << it.first << " " << it.second << "\n";
}
// cout << ans << "\n";
int s1 = np[0].size(), s2 = np[1].size();
l = 0; int r = 0;
while(true) {
if(l == s1) {
ans += s2 - r;
break;
}
if(r == s2) {
ans += s1 - l;
break;
}
int a = np[0][l].first, b = np[0][l].second;
int x = np[1][r].first, y = np[1][r].second;
if(a > x) swap(a, x), swap(b, y); // a <= x
if(b >= x) {
l++, r++;
}
else {
ans++;
a = np[0][l].first, b = np[0][l].second;
x = np[1][r].first, y = np[1][r].second;
if(a < x) l++;
else r++;
}
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
