Submission #1148071

#TimeUsernameProblemLanguageResultExecution timeMemory
1148071tito_daynorCoin Collecting (JOI19_ho_t4)C++17
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll calculateInitialMoves(ll x, ll y, ll n) {
    ll moves = 0;
    
    if (x < 1) {
        moves += (1 - x);
    } else if (x > n) {
        moves += (x - n);
    }
    
    if (y < 1) {
        moves += (1 - y);
    } else if (y > 2) {
        moves += (y - 2);
    }
    
    return moves;
}

pair<ll, ll> getValidCoords(ll x, ll y, ll n) {
    if (x < 1) x = 1;
    else if (x > n) x = n;
    
    if (y < 1) y = 1;
    else if (y > 2) y = 2;
    
    return {x, y};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<vector<int>> coins(n + 1, vector<int>(3, 0));
    ll totalMoves = 0;
    
    for (int i = 0; i < 2 * n; i++) {
        ll x, y;
        cin >> x >> y;
        
        totalMoves += calculateInitialMoves(x, y, n);
        
        auto [validX, validY] = getValidCoords(x, y, n);
        coins[validX][validY]++;
    }
    
    for (int i = 1; i <= n; i++) {
        coins[i][1]--;
        coins[i][2]--;
    }
    
    int extra1 = 0, extra2 = 0;
    for (int i = 1; i <= n; i++) {
        extra1 += coins[i][1];
        extra2 += coins[i][2];
        
        if (extra1 > 0 && extra2 < 0) {
            int transfer = min(extra1, -extra2);
            totalMoves += transfer;
            extra1 -= transfer;
            extra2 += transfer;
        } else if (extra2 > 0 && extra1 < 0) {
            int transfer = min(extra2, -extra1);
            totalMoves += transfer;
            extra2 -= transfer;
            extra1 += transfer;
        }
        
        if (i == n || (extra1 != 0 || extra2 != 0)) {
            totalMoves += abs(extra1) + abs(extra2);
            extra1 = 0;
            extra2 = 0;
        }
    }
    
    cout << totalMoves << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...