Submission #95796

#	Time	Username	Problem	Language	Result	Execution time	Memory
95796		Martomate	Palembang Bridges (APIO15_bridge)	Java	31 / 100	466 ms	55532 KiB

bridge

import java.io.*;
import java.util.*;

public class bridge {
    public static void main(String[] args) {
        Kattio io = new Kattio(System.in);

        int K = io.getInt();
        int N = io.getInt();

        long same = 0;

        ArrayList<Person> persons = new ArrayList<>();

        int maxPos = 0;

        for (int i = 0; i < N; i++) {
            char P = io.getWord().charAt(0);
            int S = io.getInt();
            char Q = io.getWord().charAt(0);
            int T = io.getInt();

            if (P == Q)
                same += Math.abs(S - T);
            else {
                persons.add(new Person(S, T));
                maxPos = Math.max(Math.max(S, T), maxPos);
            }
        }

        if (K == 1) {
            int min = 0;
            int max = maxPos;

            while (min < max) {
                int mid = (min + max) / 2;

                if (value(persons, mid) < value(persons, mid+1)) {
                    max = mid;
                } else {
                    min = mid+1;
                }
            }

            io.println(same + value(persons, min));
        } else if (K == 2) {
            int min = 0;
            int max = maxPos;

            while (min < max) {
                int mid = (min + max) / 2;

//                io.println(min + " " + mid + " " + max + " " + value2(persons, mid));

                if (value2(persons, mid) < value2(persons, mid+1)) {
                    max = mid;
                } else {
                    min = mid+1;
                }
            }

            io.println(same + value2(persons, min));
        }

        io.close();
    }

    private static long value2(ArrayList<Person> persons, int a) {
        int min = 0;
        int max = a-1;

        while (min < max) {
            int mid = (min + max) / 2;

            if (value3(persons, mid, a) < value3(persons, mid+1, a)) {
                max = mid;
            } else {
                min = mid+1;
            }
        }

        return value3(persons, min, a);
    }

    private static long value3(ArrayList<Person> persons, int l, int r) {
        long sum = 0;

        for (Person p : persons) {
            int d1 = Math.abs(p.S - l) + Math.abs(p.T - l) + 1;
            int d2 = Math.abs(p.S - r) + Math.abs(p.T - r) + 1;
            sum += Math.min(d1, d2);
        }

        return sum;
    }

    private static long value(ArrayList<Person> persons, int bridge) {
        long sum = 0;

        for (Person p : persons) {
            sum += Math.abs(p.S - bridge);
            sum += Math.abs(p.T - bridge);
            sum++;
        }

        return sum;
    }

    static class Person {
        int S, T;

        Person(int s, int t) {
            S = s;
            T = t;
        }
    }
}

class Kattio extends PrintWriter {

    public Kattio(InputStream i) {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(i));
    }
    public Kattio(InputStream i, OutputStream o) {
        super(new BufferedOutputStream(o));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }

    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }

    public String getLine() {
        token = null;
        try {
            return r.readLine();
        } catch (IOException e) {}
        return null;
    }
}

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