#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
char *stack, *send;
stack = (char *)malloc(stsize);
send = stack + stsize - 16;
send = (char *)((uintptr_t)send / 16 * 16);
asm volatile(
"mov %%rsp, (%0)\n"
"mov %0, %%rsp\n"
:
: "r"(send));
func();
asm volatile("mov (%0), %%rsp\n" : : "r"(send));
free(stack);
}
int r[3][MAXN], l[3][MAXN], ud[3][MAXN];
void solve(int tc) {
int n;
cin >> n;
int cnt[3][n+1];
for(int i=1; i<=3; i++) {
for(int j=1; j<=n; j++) {
cnt[i][j] = 0;
}
}
int ans = 0;
for(int i=1; i<=2*n; i++) {
int x, y;
cin >> x >> y;
if(x < 1) ans += 1 - x;
if(x > n) ans += x - n;
if(y < 1) ans += 1 - y;
if(y > 2) ans += y - 2;
x = max(x, 1ll);
y = max(y, 1ll);
x = min(x, n);
y = min(y, 2ll);
cnt[y][x]++;
}
vector<pair<int, int> > extra;
for(int i=1; i<=2; i++) {
for(int j=1; j<=n; j++) {
for(int k=1; k<cnt[i][j]; k++) extra.push_back({i, j});
}
}
for(pair<int,int> x: extra) {
int st = (x.first - 1) * n + x.second;
vector<pair<int,int>> adj[2*n+1];
for(int i=1; i<=2; i++) {
for(int j=1; j<=n; j++) {
int node = (i-1) * n + j;
if(j>1 && l[i][j]>=r[i][j-1]) adj[node].push_back({node-1, 1});
else if(j>1) adj[node].push_back({node-1, -1});
if(j<n && r[i][j]>=l[i][j+1]) adj[node].push_back({node+1, 1});
else if(j<n) adj[node].push_back({node+1, -1});
if(ud[i][j]>=ud[3-i][j]) adj[node].push_back({(2-i)*n+j, 1});
else adj[node].push_back({(2-i)*n+j, -1});
}
}
bool vis[2*n+1];
int dist[2*n+1], prv[2*n+1];
for(int i=1; i<=2*n; i++) {
dist[i] = 1e9;
vis[i] = 0;
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[st] = 0;
pq.push({0, st});
while(pq.size()) {
pair<int, int> t = pq.top();
pq.pop();
if(!vis[t.second]) {
vis[t.second] = 1;
for(pair<int, int> x : adj[t.second]) {
if(!vis[x.first] && dist[x.first] > dist[t.second] + x.second) {
dist[x.first] = dist[t.second] + x.second;
prv[x.first] = t.second;
pq.push({dist[x.first], x.first});
}
}
}
}
int en = -1, mn = 1e9;
for(int i=1; i<=2; i++) {
for(int j=1; j<=n; j++) {
if(!cnt[i][j]) {
int id = (i-1) * n + j;
if(dist[id] < mn) {
mn = dist[id];
en = id;
}
}
}
}
cnt[(st-1)/n+1][(st-1)%n+1]--;
cnt[(en-1)/n+1][(en-1)%n+1]++;
//cout<<st<<" -> "<<en<<"\n";
ans += dist[en];
while(en != st) {
int p = prv[en];
if(p + n == en) {
ud[1][p]++;
}
else if(p - n == en) {
ud[2][p-n]++;
}
else if(p + 1 == en) {
if(p <= n) r[1][p]++;
else r[2][p-n]++;
}
else {
if(p <= n) l[1][p]++;
else l[2][p-n]++;
}
en = p;
}
}
cout << ans << "\n";
}
void uwu() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
#ifdef ONLINE_JUDGE
uwu();
#endif
#ifndef ONLINE_JUDGE
run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
#endif
}
/*
g++ A.cpp -std=c++17 -O2 -o A
./A < input.txt
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
20 ms |
604 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
20 ms |
604 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
20 ms |
604 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
