Submission #860465

#	Time	Username	Problem	Language	Result	Execution time	Memory
860465		Oz121	Palembang Bridges (APIO15_bridge)	Java	0 / 100	50 ms	26980 KiB

bridge

import java.io.*;
import java.util.*;
public class bridge {
    public static PriorityQueue<Long> left; public static PriorityQueue<Long> right;
    public static long lSum; public static long rSum; //We have distance = \sum_{i} |S_i - bridge| + |T_i-bridge|
    //If we pick the median as the bridge (which is optimal), then there are an equal amount of S_i or T_i > bridge as < bridge
    //(if odd, the bridge = median, so difference = 0). Thus, the -x and +x all cancel, leaving distance = rSum - lSum.
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        int k = Integer.parseInt(l1.nextToken()); int tot = Integer.parseInt(l1.nextToken()); int num = 0; ArrayList<Integer> idxs = new ArrayList<>();

        long[][] arrTemp = new long[tot][4]; long constant = 0; //Distance for same shore house-work pairs.
        for (int i = 0;i<tot;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine()); String s = st.nextToken();
            arrTemp[i][0] = s.charAt(0)-'A'; arrTemp[i][1] = s.charAt(1)-'0'; arrTemp[i][2] = s.charAt(2)-'A'; arrTemp[i][3] = s.charAt(3)-'0';

            if (arrTemp[i][0]==arrTemp[i][2]) {
                constant += Math.abs(arrTemp[i][1]-arrTemp[i][3]);
            } else {
                num++; idxs.add(i);
            }
        }

        long[][] arr = new long[num][2]; //Filtered to only the house-work pairs that are not on the same bank.
        int idx = 0;
        for (int i : idxs) {
            arr[idx][0] = arrTemp[i][1]; arr[idx][1] = arrTemp[i][3]; idx++;
        }
        Arrays.sort(arr,(i,j)-> (int) ((i[0]+i[1])-(j[0]+j[1])));

        /*for (int i = 0;i<num;i++) {
            System.out.println(arr[i][0]+" "+arr[i][1]);
        }*/

        clean(); long ans;
        long[] prefix = new long[num+1]; //Prefix of all the answers if we have cows 0 to i

        for (int i = 0;i<num;i++) {
            insert(arr[i][0]); insert(arr[i][1]);
            //System.out.println(left+" "+right);
            prefix[i+1] = rSum - lSum;
        }
        ans = prefix[num];

        if (k==2) { //Iterate through all possible partitioning spots.
            clean();

            for (int i = num; i>0; i--) {
                insert(arr[i][0]); insert(arr[i][1]);
                ans = Math.min(ans, rSum - lSum + prefix[i - 1]);
            }
        }

        System.out.println(ans+constant+num);
    }

    public static void insert (long x) {
        long median = (left.size()>0 ? left.peek() : 1000000001);

        if (x<=median) { //Insert to left
            left.add(x); lSum += x;
        } else { //Insert to right
            right.add(x); rSum += x;
        }

        //Check sizes. We want left.size = right.size + (0 or 1)
        if (right.size()+1<left.size()) { //Add to right
            long temp = left.peek();
            left.poll(); right.add(temp);
            lSum -= temp; rSum += temp;
        } else if (left.size()<right.size()) { //Add to left
            long temp = right.peek();
            right.poll(); left.add(temp);
            rSum -= temp; lSum += temp;
        }
    }

    public static void clean () {
        left = new PriorityQueue<>((a,b)-> (int) (b-a)); right = new PriorityQueue<>((a,b)-> (int) (a-b));
        lSum = 0; rSum = 0;
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37