#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <memory.h>
#include <cmath>
#include <array>
using namespace std;
void re(int& x);
template<class T, class... Ts> void re(T& t, Ts&... ts);
void pr(long long x);
void pr(const char *x);
void ps();
template<class T, class... Ts> void ps(const T& t, const Ts&... ts);
#ifdef FFDBG
#else
#define dbg(x...) dsfdsfsdfasd
#endif
void re(int& x) { scanf("%d", &x); }
template<class T, class... Ts> void re(T& t, Ts&... ts) {
re(t); re(ts...);
}
void pr(long long x) { printf("%lld", x); }
void pr(const char *x) { printf("%s", x); }
void ps() { pr("\n"); }
template<class T, class... Ts> void ps(const T& t, const Ts&... ts) {
pr(t); if (sizeof...(ts)) pr(" "); ps(ts...);
}
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
int n;
int coins[100010][3];
vector< int > fr[2];
vector< int > b[2];
void solve()
{
long long ans = 0;
re(n);
rep(i,0,2*n) {
int x,y;
re(x,y);
if (x < 1) {
ans += 1-x;
x = 1;
}
if (x > n) {
ans += x-n;
x = n;
}
if (y < 1) {
ans += 1-y;
y = 1;
}
if (y > 2) {
ans += y-2;
y = 2;
}
x--; y--;
//dbg(x,y);
coins[x][y]++;
}
rep(x,0,n) rep(y,0,2) if (!coins[x][y]) fr[y].push_back(x);
rep(i,0,2) sort(all(fr[i]));
rep(x,0,n) {
rep(y,0,2) if (!b[y].empty()) {
if (coins[x][y] == 0) {
ans += x - b[y].back();
b[y].pop_back();
fr[y].pop_back();
coins[x][y]++;
}
if (coins[x][1-y] == 0 && !b[y].empty() && b[1-y].empty()) {
ans += x - b[y].back() + 1;
b[y].pop_back();
fr[1-y].pop_back();
coins[x][1-y]++;
}
}
rep(y,0,2) {
while (coins[x][y] > 1) {
if (!fr[y].empty() && fr[y].back() <= x) {
ans += x - fr[y].back();
fr[y].pop_back();
}
else if (!fr[1-y].empty() && fr[1-y].back() <= x) {
if (coins[x][1-y] > 1) {
coins[x][1-y]--;
ans += x - fr[1-y].back();
fr[1-y].pop_back();
continue;
}
ans += x - fr[1-y].back() + 1;
fr[1-y].pop_back();
}
else b[y].push_back(x);
coins[x][y]--;
}
}
}
//dbg(sz(b[0]), sz(b[1]));
ps(ans);
}
int main() {
solve();
}
Compilation message
joi2019_ho_t4.cpp: In function 'void re(int&)':
joi2019_ho_t4.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void re(int& x) { scanf("%d", &x); }
~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |