//bit chass 1
#include <bits/stdc++.h>
#define x first
#define y second
#define el "\n"
#define ll long long
#define pb push_back
#define pll pair <ll, ll>
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define lcm(x,y) x * y / __gcd(x, y)
#define ibase ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 7, M = 2e6, MM = 2e6 + 5, K = 300;
const ll MI = 2e18;
const double P = 3.14;
ll c[3][N];
string sum(string a, string b) {
string c = "";
int s, o = 0;
if (a.size() < b.size()) swap(a, b);
reverse(all(a));
reverse(all(b));
for (int i = 0; i < b.size(); i++) {
s = (a[i] - '0') + (b[i] - '0') + o;
c += (s % 10) + '0';
o = s / 10;
}
for (int i = b.size(); i < a.size(); i++) {
s = (a[i] - '0') + o;
c += (s % 10) + '0';
o = s / 10;
}
if (o != 0) c += o + '0';
reverse(all(c));
return c;
}
string ms(ll k) {
string a = "";
while (k)
a += (char)(48 + k % 10), k /= 10;
reverse(all(a));
return a;
}
void solve() {
ll n;
string ans = "0";
ll k;
cin >> n;
for (int i = 1; i <= 2 * n; i++) {
ll x, y;
cin >> x >> y;
if (1 <= x && x <= n && 1 <= y && y <= 2)
c[y][x]++;
else if (1 <= x && x <= n) {
if (y <= 0)
c[1][x]++, ans = sum(ans, ms(1 - y));
else
c[2][x]++, ans = sum(ans, ms( y - 2));
}
else if (1 <= y && y <= 2) {
if (x <= 0)
c[y][1]++, ans = sum(ans, ms(1 - x));
else
c[y][n]++, ans = sum(ans, ms(x - n));
}
else {
if (x <= 0 && y <= 0)
c[1][1]++, ans = sum(ans, ms(1 - y + 1 - x));
if (x <= 0 && y > 2)
c[2][1]++, ans = sum(ans, ms(1 - x + y - 2));
if (x > n && y <= 0)
c[1][n]++, ans = sum(ans, ms(x - n + 1 - y));
if (x > n && y > 2)
c[2][n]++, ans = sum(ans, ms(x - n + y - 2));
}
}
int r = 1;
for (int i = 1; i <= n; i++) {
r = max(i, r);
if (c[1][i] && c[2][i]) {
c[1][i]--;
c[2][i]--;
ans = sum(ans, ms(c[1][i]));
ans = sum(ans, ms(c[2][i]));
c[1][i + 1] += c[1][i];
c[2][i + 1] += c[2][i];
}
else if (c[1][i]) {
if (c[1][i] >= 2) {
c[2][i]++;
ans = sum(ans, ms(1ll));
c[1][i] -= 2;
c[1][i + 1] += c[1][i];
ans = sum(ans, ms(c[1][i]));
}
else {
r = max(r, i + 1);
while (c[1][r] + c[2][r] == 0)
r++;
if (c[2][r]) {
ans = sum(ans, ms(r - i));
c[2][r]--;
c[2][i]++;
}
else {
ans = sum(ans, ms(r - i + 1));
c[1][r]--;
c[2][i]++;
}
}
}
else if (c[2][i]) {
if (c[2][i] >= 2) {
c[1][i]++;
ans = sum(ans, ms(1ll));
c[2][i] -= 2;
c[2][i + 1] += c[2][i];
ans = sum(ans, ms(c[2][i]));
}
else {
r = max(r, i + 1);
while (c[1][r] + c[2][r] == 0)
r++;
if (c[1][r]) {
ans = sum(ans, ms(r - i));
c[1][i]++;
c[1][r]--;
}
else {
ans = sum(ans, ms(r - i + 1));
c[2][r]--;
c[1][i]++;
}
}
}
else {
while (c[1][r] + c[2][r] == 0)
r++;
if (c[1][r]) {
c[1][i]++;
ans = sum(ans, ms(r - i));
c[1][r]--;
if (c[2][r]) {
c[2][i]++;
ans = sum(ans, ms(r - i));
c[2][r]--;
}
else {
while (c[1][r] + c[2][r] == 0)
r++;
if (c[2][r]) {
ans = sum(ans, ms(r - i));
c[2][r]--;
c[2][i]++;
}
else {
ans = sum(ans, ms(r - i + 1));
c[1][r]--;
c[2][i]++;
}
}
}
else if (c[2][r]) {
c[2][i]++;
ans = sum(ans, ms(r - i));
c[2][r]--;
if (c[1][r]) {
c[1][i]++;
ans = sum(ans, ms(r - i));
c[1][r]--;
}
else {
while (c[1][r] + c[2][r] == 0)
r++;
if (c[1][r]) {
ans = sum(ans, ms(r - i));
c[1][i]++;
c[1][r]--;
}
else {
ans = sum(ans, ms(r - i + 1));
c[2][r]--;
c[1][i]++;
}
}
}
}
}
cout << ans;
}
int main() {
ibase;
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++) {
// cout << "Case " << i << ": ";
solve();
cout << el;
}
}
Compilation message
joi2019_ho_t4.cpp: In function 'std::string sum(std::string, std::string)':
joi2019_ho_t4.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < b.size(); i++) {
| ~~^~~~~~~~~~
joi2019_ho_t4.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = b.size(); i < a.size(); i++) {
| ~~^~~~~~~~~~
joi2019_ho_t4.cpp: In function 'void solve()':
joi2019_ho_t4.cpp:55:5: warning: unused variable 'k' [-Wunused-variable]
55 | ll k;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
