#include<bits/stdc++.h>
using namespace std;
const int MX = 1e5 + 5;
const int INF = 1e9;
int n;
int a[2][MX];
int nxt(int i, int j) {
for(; j<n; ++j) {
if(a[i][j]) return j;
}
return INF;
}
long long solve() {
int rem1 = accumulate(a[0], a[0]+n, 0), rem2 = accumulate(a[1], a[1]+n, 0);
long long ret = 0;
for(int i=0; i<n-1; ++i) {
if(a[0][i]>0 && a[1][i]>0) {
ret += a[0][i]-1 + a[1][i]-1;
a[0][i+1] += a[0][i]-1;
a[1][i+1] += a[1][i]-1;
a[0][i] = a[1][i] = 1;
}
if(a[0][i]==0 && a[1][i]==0) {
int j=nxt(0, i+1), k=nxt(1, i+1);
if(j<k) {
a[0][j]--, a[0][i]++;
ret += j-i;
} else {
a[1][k]--, a[1][i]++;
ret += k-i;
}
}
if(a[0][i]==0) {
if(a[1][i]>1) {
--rem2;
++rem1;
a[1][i]--, a[0][i]++;
ret += 1;
goto outside;
}
int j=nxt(0, i+1), k=nxt(1, i+1);
if(j>k+1 || (j==k+1 && rem1<rem2)) {
ret += k-i+1;
++rem1;
--rem2;
a[1][k]--, a[0][i]++;
} else {
ret += j-i;
a[0][j]--, a[0][i]++;
}
} outside:
if(a[1][i]==0) {
if(a[0][i]>1) {
--rem1, ++rem2;
a[0][i]--, a[1][i]++;
ret += 1;
goto outside2;
}
int j=nxt(0, i+1), k=nxt(1, i+1);
if(j+1<k || (j+1==k && rem2<rem1)) {
ret += j-i+1;
--rem1;
++rem2;
a[0][j]--, a[1][i]++;
} else {
ret += k-i;
a[1][k]--, a[1][i]++;
}
} outside2:
if(a[0][i]>1) {
a[0][i+1] += a[0][i]-1;
ret += a[0][i]-1;
}
if(a[1][i]>1) {
a[1][i+1] += a[1][i]-1;
ret += a[1][i]-1;
}
--rem1, --rem2;
//cerr<<ret<<endl;
}
if(~a[0][n-1]&1) ++ret;
return ret;
}
void PlayGround() {
cin>>n;
long long cost = 0;
for(int i=0; i<2*n; ++i) {
int x, y;
cin>>x>>y;
swap(x, y);
if(x<=1) {
cost += 1-x;
x = 0;
} else {
cost += x-2;
x = 1;
}
if(y<1) {
cost += 1-y;
y = 1;
}
if(y>n) {
cost += y-n;
y = n;
}
--y;
a[x][y]++;
}
// cerr<<cost<<endl;
// for(int i=0; i<n; ++i) {
// cerr<<a[0][i]<<' '<<a[1][i]<<endl;
// }
cout<<solve()+cost<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |