Submission #439711

#	Time	Username	Problem	Language	Result	Execution time	Memory
439711		idontreallyknow	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	72 ms	5700 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define SZ(x) ((int)((x).size()))
#define debug(x) cerr << #x << " = " << x << '\n'
const int mx = 1e5+5;
int ct[mx][2], tot[2];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    ll ans = 0;
    for (int q = 0; q < 2*n; q++) {
        int a,b;
        cin >> a >> b;
        int x = a, y = b;
        if (a < 1) ans += 1-a, x = 1;
        if (a > n) ans += a-n, x = n;
        if (b < 1) ans += 1-b, y = 1;
        if (b > 2) ans += b-2, y = 2;
        y--;
        ct[x][y]++;
    }
    for (int q = 1; q <= n; q++) for (int w = 0; w <= 1; w++) ct[q][w]--;
    int t = 0; //0 = coin, 1 = blank
    for (int q = 1; q <= n; q++) {
        ans += tot[0]+tot[1];
        if (t == 0) {
            if (ct[q][0] > 0) tot[0] += ct[q][0], ct[q][0] = 0;
            if (ct[q][1] > 0) tot[1] += ct[q][1], ct[q][1] = 0;
            if (ct[q][0] < 0 && tot[0] > 0) tot[0]--, ct[q][0] = 0;
            if (ct[q][1] < 0 && tot[1] > 0) tot[1]--, ct[q][1] = 0;
            if (ct[q][0] == -1 && tot[1] > 0) ans++, ct[q][0] = 0, tot[1]--;
            if (ct[q][1] == -1 && tot[0] > 0) ans++, ct[q][1] = 0, tot[0]--;
            if (ct[q][0] == -1 || ct[q][1] == -1) t = 1, tot[0] = -ct[q][0], tot[1] = -ct[q][1];
        } else {
            if (ct[q][0] < 0) tot[0]++, ct[q][0] = 0;
            if (ct[q][1] < 0) tot[1]++, ct[q][1] = 0;
            if (ct[q][0] > 0 && tot[0] > 0) {
                int x = min(ct[q][0], tot[0]);
                ct[q][0] -= x;
                tot[0] -= x;
            }
            if (ct[q][1] > 0 && tot[1] > 0) {
                int x = min(ct[q][1], tot[1]);
                ct[q][1] -= x;
                tot[1] -= x;
            }
            if (ct[q][1] > 0 && tot[0] > 0) {
                int x = min(ct[q][1], tot[0]);
                ct[q][1] -= x;
                tot[0] -= x;
                ans += x;
            }
            if (ct[q][0] > 0 && tot[1] > 0) {
                int x = min(ct[q][0], tot[1]);
                ct[q][0] -= x;
                tot[1] -= x;
                ans += x;
            }
            if (ct[q][0] > 0 || ct[q][1] > 0) t = 0, tot[0] = ct[q][0], tot[1] = ct[q][1];
        }
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63