Submission #1147250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147250		paolaparedes	Coin Collecting (JOI19_ho_t4)	Java	100 / 100	833 ms	163840 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {

    static int maxColumn;
    static int[][] coinsMatrix;
    static long moveCount;

    static Stack<Integer>[] surplusStacks;
    static Stack<Integer>[] deficitStacks;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        maxColumn = sc.nextInt();
        int totalCoins = 2 * maxColumn;
        coinsMatrix = new int[3][maxColumn + 1];
        moveCount = 0;

        for (int i = 0; i < totalCoins; i++){
            int c = sc.nextInt();
            int r = sc.nextInt();

            moveCount += movesToBoundary(c, r);

            int validR = clamp(r, 1, 2);
            int validC = clamp(c, 1, maxColumn);
            coinsMatrix[validR][validC]++;
        }

        initializeStacks();

        for(int currentCol = 1; currentCol <= maxColumn; currentCol++){
            distributeCoins(currentCol);
        }

        System.out.println(moveCount);
    }


    private static void distributeCoins(int col) {

        for (int row = 1; row <= 2; row++){
            if(coinsMatrix[row][col] == 0 && !surplusStacks[row].isEmpty()){
                int fromCol = surplusStacks[row].peek();

                coinsMatrix[row][fromCol]--;
                coinsMatrix[row][col]++;
                moveCount += Math.abs(col - fromCol);

                if(coinsMatrix[row][fromCol] == 1) {
                    surplusStacks[row].pop();
                }
            }
        }


        for (int row = 1; row <= 2; row++){
            while(coinsMatrix[row][col] > 1 && !deficitStacks[row].isEmpty()){
                int emptyCol = deficitStacks[row].peek();
                coinsMatrix[row][col]--;
                coinsMatrix[row][emptyCol]++;
                moveCount += Math.abs(col - emptyCol);
                deficitStacks[row].pop();
            }
        }

        for (int row = 1; row <= 2; row++){
            int other = (row == 1) ? 2 : 1;
            if(coinsMatrix[row][col] == 0 && !surplusStacks[other].isEmpty()){
                int fromCol = surplusStacks[other].peek();
                coinsMatrix[other][fromCol]--;
                coinsMatrix[row][col]++;
                moveCount += Math.abs(col - fromCol) + 1;
                if(coinsMatrix[other][fromCol] == 1) {
                    surplusStacks[other].pop();
                }
            }
        }

        for (int row = 1; row <= 2; row++){
            int other = (row == 1) ? 2 : 1;
            while(coinsMatrix[row][col] > 1 && !deficitStacks[other].isEmpty()){
                int emptyCol = deficitStacks[other].peek();
                coinsMatrix[row][col]--;
                coinsMatrix[other][emptyCol]++;
                moveCount += Math.abs(col - emptyCol) + 1;
                deficitStacks[other].pop();
            }
        }
        if(coinsMatrix[1][col] > 1 && coinsMatrix[2][col] == 0){
            coinsMatrix[1][col]--;
            coinsMatrix[2][col]++;
            moveCount++;
        }
        else if(coinsMatrix[2][col] > 1 && coinsMatrix[1][col] == 0){
            coinsMatrix[2][col]--;
            coinsMatrix[1][col]++;
            moveCount++;
        }


        for(int row = 1; row <= 2; row++){
            if(coinsMatrix[row][col] > 1){
                surplusStacks[row].push(col);
            }
            else if(coinsMatrix[row][col] == 0){
                deficitStacks[row].push(col);
            }
        }
    }

    private static long movesToBoundary(int c, int r){
        long moves = 0;

        if(r < 1) moves += (1 - r);
        if(r > 2) moves += (r - 2);
        if(c < 1) moves += (1 - c);
        if(c > maxColumn) moves += (c - maxColumn);
        return moves;
    }

    private static int clamp(int value, int min, int max){
        if(value < min) return min;
        if(value > max) return max;
        return value;
    }

    private static void initializeStacks(){
        surplusStacks = new Stack[3];
        deficitStacks = new Stack[3];
        for (int i = 0; i < 3; i++){
            surplusStacks[i] = new Stack<>();
            deficitStacks[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