Submission #1148070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148070		tito_daynor	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	0 ms	324 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

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

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 += bfs(x, y, n);
        
        if (x >= 1 && x <= n && y >= 1 && y <= 2) {
            coins[x][y]++;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        coins[i][1]--;
        coins[i][2]--;
        
        if (coins[i][1] > 0 && coins[i][2] < 0) {
            int moves = min(coins[i][1], -coins[i][2]);
            totalMoves += moves;
            coins[i][1] -= moves;
            coins[i][2] += moves;
        } else if (coins[i][2] > 0 && coins[i][1] < 0) {
            int moves = min(coins[i][2], -coins[i][1]);
            totalMoves += moves;
            coins[i][2] -= moves;
            coins[i][1] += moves;
        }
        
        if (i < n) {
            coins[i + 1][1] += coins[i][1];
            coins[i + 1][2] += coins[i][2];
        }
        totalMoves += abs(coins[i][1]) + abs(coins[i][2]);
    }
    
    cout << totalMoves << "\n";
    return 0;
}

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