Submission #1126462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126462		irmuun	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	0 ms	328 KiB

joi2019_ho_t4

// ChatGPT 4o mini

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define int long long

struct Cell {
    int row, col, coins;
    Cell(int r, int c, int coin_count) : row(r), col(c), coins(coin_count) {}
};

// Function to calculate minimum cost to make all cells contain exactly 1 coin
int min_cost_to_redistribute(int n, vector<vector<int>>& a) {
    vector<Cell> cells;
    
    // Step 1: Populate the cells list with the position and coin counts
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            cells.push_back(Cell(i, j, a[i][j]));
        }
    }

    // Step 2: Sort the cells by row and then by column (row-major order)
    sort(cells.begin(), cells.end(), [](const Cell& c1, const Cell& c2) {
        return c1.row < c2.row || (c1.row == c2.row && c1.col < c2.col);
    });

    int total_cost = 0;
    
    // Step 3: Separate cells into excess and deficit
    vector<Cell> excess, deficit;

    for (auto& cell : cells) {
        if (cell.coins > 1) {
            excess.push_back(Cell(cell.row, cell.col, cell.coins - 1));  // excess coins
        } else if (cell.coins < 1) {
            deficit.push_back(Cell(cell.row, cell.col, 1 - cell.coins));  // deficit coins
        }
    }

    int ex_idx = 0, de_idx = 0;

    // Step 4: Move coins from excess to deficit
    while (ex_idx < excess.size() && de_idx < deficit.size()) {
        // Determine how many coins to move
        int move = min(excess[ex_idx].coins, deficit[de_idx].coins);
        
        // Calculate cost of moving these coins
        int cost = move * (abs(excess[ex_idx].row - deficit[de_idx].row) + abs(excess[ex_idx].col - deficit[de_idx].col));
        total_cost += cost;

        // Update the remaining coins in excess and deficit
        excess[ex_idx].coins -= move;
        deficit[de_idx].coins -= move;

        // Move to the next excess or deficit if no more coins need to be moved
        if (excess[ex_idx].coins == 0) {
            ++ex_idx;
        }
        if (deficit[de_idx].coins == 0) {
            ++de_idx;
        }
    }

    return total_cost;
}

signed main() {
    // Example input
    int n;
    cin>>n;
    vector<vector<int>>a(2*n);
    for(int i=0;i<2*n;i++){
        a[i].resize(2);
        cin>>a[i][0]>>a[i][1];
    }
    int ans=0;
    for(int i=0;i<2*n;i++){
        if(a[i][0]<1){
            ans+=1-a[i][0];
            a[i][0]=1;
        }
        if(a[i][0]>n){
            ans+=a[i][0]-n;
            a[i][0]=n;
        }
        if(a[i][1]<1){
            ans+=1-a[i][1];
            a[i][1]=1;
        }
        if(a[i][1]>2){
            ans+=a[i][1]-2;
            a[i][1]=2;
        }
    }
    vector<vector<int>>c(n);
    for(int i=0;i<n;i++){
        c[i].resize(2);
    }
    for(int i=0;i<2*n;i++){
        c[a[i][0]-1][a[i][1]-1]++;
    }
    // Compute the minimum cost
    int result = min_cost_to_redistribute(n, c);
    cout << ans + result << endl;

    return 0;
}

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