#include "bits/stdc++.h"
#define int long long
using namespace std;
struct coin {
int ox, oy; // original x, y
int nx, ny; // new x, y
int cost = 0;
};
void solve(int tc) {
int n;
cin >> n;
coin c[2*n + 1];
for(int i=1; i<=2*n; i++) {
cin >> c[i].ox >> c[i].oy;
if(c[i].ox > n) {
if(c[i].oy >= 2) { // Choose (n, 2)
c[i].nx = n;
c[i].ny = 2;
}
else { // Choose (n, 1)
c[i].nx = n;
c[i].ny = 1;
}
}
else if(c[i].ox < 1) {
if(c[i].oy >= 2) {
c[i].nx = 1;
c[i].ny = 2;
}
else {
c[i].nx = 1;
c[i].ny = 1;
}
}
else {
if(c[i].oy >= 2) {
c[i].nx = c[i].ox;
c[i].ny = 2;
}
else {
c[i].nx = c[i].ox;
c[i].ny = 1;
}
}
c[i].cost = abs(c[i].ox - c[i].nx) + abs(c[i].oy - c[i].ny);
}
int base = 0;
for(int i=1; i<=2*n; i++) base += c[i].cost;
int cnt[n+1][3];
for(int i=1; i<=n; i++) {
for(int j=1; j<=2; j++) {
cnt[i][j] = 0;
}
}
for(int i=1; i<=2*n; i++) cnt[c[i].nx][c[i].ny]++;
queue<pair<int, int> > zero, pos;
for(int i=1; i<=n; i++) {
for(int j=1; j<=2; j++) {
if(cnt[i][j] == 0) {
int ans = 1e9;
int kk = -1, ll = -1;
for(int k=1; k<=n; k++) {
for(int l=1; l<=2; l++) {
if(cnt[k][l] <= 1) continue;
int oo = abs(i - k) + abs(j - l);
if(oo < ans) {
ans = oo;
kk = k, ll = l;
}
}
}
cnt[i][j]++;
cnt[kk][ll]--;
base += ans;
}
}
}
cout << base << '\n';
}
int32_t main() {
int t = 1;
// cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |