Submission #1148105

#TimeUsernameProblemLanguageResultExecution timeMemory
1148105humerez_sCoin Collecting (JOI19_ho_t4)Java
100 / 100
625 ms167788 KiB
import java.util.*;

public class joi2019_ho_t4 {
    static final int MAX_CELLS = 100010;
    static int numCoins;
    static int[][] grid = new int[MAX_CELLS][3];
    static long moves = 0;

    public static void processCoordinates(int x, int y) {
        if (x < 1) {
            moves += (y >= 2) ? moveCoin(1, 2, x, y) : moveCoin(1, 1, x, y);
        } else if (x <= numCoins) {
            moves += (y >= 2) ? moveCoin(x, 2, x, y) : moveCoin(x, 1, x, y);
        } else {
            moves += (y >= 2) ? moveCoin(numCoins, 2, x, y) : moveCoin(numCoins, 1, x, y);
        }
    }

    private static long moveCoin(int targetX, int targetY, int currentX, int currentY) {
        grid[targetX][targetY]++;
        return Math.abs(currentX - targetX) + Math.abs(currentY - targetY);
    }

    public static void solve() {
        long misplacedRow1 = 0, misplacedRow2 = 0;
        for (int i = 1; i <= numCoins; i++) {
            misplacedRow1 += (grid[i][1] - 1);
            misplacedRow2 += (grid[i][2] - 1);

            while (misplacedRow1 > 0 && misplacedRow2 < 0) {
                misplacedRow1--;
                misplacedRow2++;
                moves++;
            }
            while (misplacedRow1 < 0 && misplacedRow2 > 0) {
                misplacedRow1++;
                misplacedRow2--;
                moves++;
            }

            moves += Math.abs(misplacedRow1) + Math.abs(misplacedRow2);
        }
    }

    public static void readInput(Scanner scanner) {
        numCoins = scanner.nextInt();
        for (int i = 1; i <= 2 * numCoins; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            processCoordinates(x, y);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        readInput(scanner);
        solve();
        System.out.println(moves);
        scanner.close();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...