Submission #1146894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146894		mamaniever	Coin Collecting (JOI19_ho_t4)	Java	100 / 100	743 ms	197568 KiB

joi2019_ho_t4

import java.util.*;

class joi2019_ho_t4 {
    static int gridWidth;
    static int[][] coinsInCell;
    static long totalMoves = 0;
    static Stack<Integer>[] excessCoins;
    static Stack<Integer>[] emptySpaces;

    public static void moveCoinsInColumn(int column) {
        if(column > gridWidth) return;
        
        // Mover monedas del mismo nivel
        for (int row = 1; row <= 2; row++) {
            if(coinsInCell[row][column] == 0 && !excessCoins[row].isEmpty()){
                int sourceCol = excessCoins[row].peek();
                totalMoves += Math.abs(column - sourceCol);
                coinsInCell[row][sourceCol]--;
                if(coinsInCell[row][sourceCol] == 1) excessCoins[row].pop();
                coinsInCell[row][column]++;
            }
        }

        // Redistribuir monedas extra
        for (int row = 1; row <= 2; row++) {
            while(!emptySpaces[row].isEmpty() && coinsInCell[row][column] > 1){
                int sourceCol = emptySpaces[row].peek();
                totalMoves += Math.abs(column - sourceCol);
                coinsInCell[row][sourceCol]++;
                emptySpaces[row].pop();
                coinsInCell[row][column]--;
            }
        }

        // Mover monedas entre niveles
        for (int row = 1; row <= 2; row++) {
            int otherRow = 3 - row;
            if(coinsInCell[row][column] == 0 && !excessCoins[otherRow].isEmpty()){
                int sourceCol = excessCoins[otherRow].peek();
                totalMoves += Math.abs(column - sourceCol) + 1;
                coinsInCell[otherRow][sourceCol]--;
                if(coinsInCell[otherRow][sourceCol] == 1) excessCoins[otherRow].pop();
                coinsInCell[row][column]++;
            }
        }

        // Redistribuir monedas extra entre niveles
        for (int row = 1; row <= 2; row++) {
            int otherRow = 3 - row;
            while(!emptySpaces[otherRow].isEmpty() && coinsInCell[row][column] > 1){
                int sourceCol = emptySpaces[otherRow].peek();
                totalMoves += Math.abs(column - sourceCol) + 1;
                coinsInCell[otherRow][sourceCol]++;
                emptySpaces[otherRow].pop();
                coinsInCell[row][column]--;
            }
        }

        // Balancear monedas en la columna actual
        for (int row = 1; row <= 2; row++) {
            int otherRow = 3 - row;
            if(coinsInCell[row][column] > 1 && coinsInCell[otherRow][column] == 0){
                coinsInCell[row][column]--;
                coinsInCell[otherRow][column]++;
                totalMoves++;
            }
        }

        // Actualizar estados de la columna
        for (int row = 1; row <= 2; row++) {
            if(coinsInCell[row][column] > 1) excessCoins[row].push(column);
            if(coinsInCell[row][column] == 0) emptySpaces[row].push(column);
        }

        moveCoinsInColumn(column + 1);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        gridWidth = sc.nextInt();
        int totalCoins = 2 * gridWidth;
        coinsInCell = new int[3][gridWidth + 1];
        totalMoves = 0;

        // Procesar posiciones iniciales
        for (int i = 0; i < totalCoins; i++){
            int col = sc.nextInt(), row = sc.nextInt();
            totalMoves += calculateBoundaryMoves(row, col);
            row = normalizeCoordinate(row, 1, 2);
            col = normalizeCoordinate(col, 1, gridWidth);
            coinsInCell[row][col]++;
        }

        initializeStacks();
        moveCoinsInColumn(1);
        System.out.println(totalMoves);
    }

    private static long calculateBoundaryMoves(int row, int col) {
        long moves = 0;
        if(row < 1) moves += (1 - row);
        if(row > 2) moves += (row - 2);
        if(col < 1) moves += (1 - col);
        if(col > gridWidth) moves += (col - gridWidth);
        return moves;
    }

    private static int normalizeCoordinate(int value, int min, int max) {
        return Math.max(min, Math.min(max, value));
    }

    private static void initializeStacks() {
        excessCoins = new Stack[3];
        emptySpaces = new Stack[3];
        for (int i = 0; i < 3; i++){
            excessCoins[i] = new Stack<>();
            emptySpaces[i] = new Stack<>();
        }
    }
}

Compilation message (stderr)

Note: joi2019_ho_t4.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

=======

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