Submission #1145575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145575		machaca_rodrigo	Coin Collecting (JOI19_ho_t4)	Java	100 / 100	785 ms	203868 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {
    static int n;
    static int[][] cnt;
    static long ans = 0;
    static Stack<Integer>[] extra;
    static Stack<Integer>[] zero;
    public static void processColumn(int j) {
        if(j > n) return;
        for (int i = 1; i <= 2; i++) {
            if(cnt[i][j] == 0 && !extra[i].isEmpty()){
                int from = extra[i].peek();
                ans += Math.abs(j - from);
                cnt[i][from]--;
                if(cnt[i][from] == 1) extra[i].pop();
                cnt[i][j]++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            while(!zero[i].isEmpty() && cnt[i][j] > 1){
                int from = zero[i].peek();
                ans += Math.abs(j - from);
                cnt[i][from]++;
                zero[i].pop();
                cnt[i][j]--;
            }
        }
        for (int i = 1; i <= 2; i++) {
            int other = 3 - i;
            if(cnt[i][j] == 0 && !extra[other].isEmpty()){
                int from = extra[other].peek();
                ans += Math.abs(j - from) + 1;
                cnt[other][from]--;
                if(cnt[other][from] == 1) extra[other].pop();
                cnt[i][j]++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            int other = 3 - i;
            while(!zero[other].isEmpty() && cnt[i][j] > 1){
                int from = zero[other].peek();
                ans += Math.abs(j - from) + 1;
                cnt[other][from]++;
                zero[other].pop();
                cnt[i][j]--;
            }
        }
        for (int i = 1; i <= 2; i++) {
            int other = 3 - i;
            if(cnt[i][j] > 1 && cnt[other][j] == 0){
                cnt[i][j]--;
                cnt[other][j]++;
                ans++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            if(cnt[i][j] > 1) extra[i].push(j);
            if(cnt[i][j] == 0) zero[i].push(j);
        }
        processColumn(j + 1);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int total = 2 * n;
        cnt = new int[3][n + 1];
        ans = 0;
        for (int i = 0; i < total; i++){
            int c = sc.nextInt(), r = sc.nextInt();
            if(r < 1){ ans += (1 - r); r = 1; }
            if(r > 2){ ans += (r - 2); r = 2; }
            if(c < 1){ ans += (1 - c); c = 1; }
            if(c > n){ ans += (c - n); c = n; }
            cnt[r][c]++;
        }
        extra = new Stack[3];
        zero = new Stack[3];
        for (int i = 0; i < 3; i++){
            extra[i] = new Stack<>();
            zero[i] = new Stack<>();
        }
        processColumn(1);
        System.out.println(ans);
    }
}

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