oj.uz

Submission #95796

# Submission time Handle Problem Language Result Execution time Memory
95796 2019-02-02T16:28:26 Z Martomate Palembang Bridges (APIO15_bridge) Java 11
31 / 100
 466 ms 55532 KB 
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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 9720 KB Output is correct
2 Correct 69 ms 9708 KB Output is correct
3 Correct 88 ms 10360 KB Output is correct
4 Correct 98 ms 10868 KB Output is correct
5 Correct 108 ms 11124 KB Output is correct
6 Correct 98 ms 10864 KB Output is correct
7 Correct 134 ms 11464 KB Output is correct
8 Correct 104 ms 10940 KB Output is correct
9 Correct 120 ms 12016 KB Output is correct
10 Correct 100 ms 10764 KB Output is correct
11 Correct 110 ms 10884 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9612 KB Output is correct
2 Correct 76 ms 9652 KB Output is correct
3 Correct 96 ms 10408 KB Output is correct
4 Correct 109 ms 10380 KB Output is correct
5 Correct 111 ms 11024 KB Output is correct
6 Correct 108 ms 10500 KB Output is correct
7 Correct 127 ms 11836 KB Output is correct
8 Correct 114 ms 10744 KB Output is correct
9 Correct 120 ms 10960 KB Output is correct
10 Correct 111 ms 11000 KB Output is correct
11 Correct 112 ms 10364 KB Output is correct
12 Correct 382 ms 52140 KB Output is correct
13 Correct 466 ms 55472 KB Output is correct
14 Correct 434 ms 47376 KB Output is correct
15 Correct 400 ms 39456 KB Output is correct
16 Correct 414 ms 54144 KB Output is correct
17 Correct 426 ms 55076 KB Output is correct
18 Correct 432 ms 53484 KB Output is correct
19 Correct 457 ms 55532 KB Output is correct
20 Correct 386 ms 52464 KB Output is correct
21 Correct 457 ms 53532 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 9584 KB Output is correct
2 Correct 75 ms 9628 KB Output is correct
3 Correct 80 ms 10100 KB Output is correct
4 Correct 113 ms 10456 KB Output is correct
5 Correct 92 ms 10148 KB Output is correct
6 Correct 93 ms 10048 KB Output is correct
7 Correct 112 ms 10500 KB Output is correct
8 Correct 115 ms 10748 KB Output is correct
9 Correct 113 ms 10532 KB Output is correct
10 Correct 106 ms 10536 KB Output is correct
11 Correct 107 ms 10744 KB Output is correct
12 Correct 111 ms 10612 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9764 KB Output is correct
2 Correct 71 ms 9524 KB Output is correct
3 Correct 82 ms 9852 KB Output is correct
4 Correct 116 ms 10696 KB Output is correct
5 Correct 96 ms 10212 KB Output is correct
6 Correct 87 ms 10120 KB Output is correct
7 Correct 113 ms 10656 KB Output is correct
8 Correct 111 ms 10588 KB Output is correct
9 Correct 114 ms 10744 KB Output is correct
10 Correct 116 ms 10744 KB Output is correct
11 Correct 114 ms 10660 KB Output is correct
12 Correct 113 ms 10652 KB Output is correct
13 Correct 100 ms 10644 KB Output is correct
14 Correct 126 ms 10868 KB Output is correct
15 Correct 170 ms 11144 KB Output is correct
16 Correct 84 ms 10136 KB Output is correct
17 Correct 110 ms 10312 KB Output is correct
18 Correct 124 ms 10740 KB Output is correct
19 Correct 173 ms 11164 KB Output is correct
20 Correct 179 ms 12364 KB Output is correct
21 Correct 154 ms 10848 KB Output is correct
22 Correct 168 ms 11860 KB Output is correct
23 Incorrect 173 ms 11060 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 9732 KB Output is correct
2 Correct 74 ms 9568 KB Output is correct
3 Correct 76 ms 9984 KB Output is correct
4 Correct 104 ms 10640 KB Output is correct
5 Correct 86 ms 10264 KB Output is correct
6 Correct 86 ms 10256 KB Output is correct
7 Correct 110 ms 10576 KB Output is correct
8 Correct 106 ms 10548 KB Output is correct
9 Correct 106 ms 10540 KB Output is correct
10 Correct 106 ms 10580 KB Output is correct
11 Correct 102 ms 10612 KB Output is correct
12 Correct 127 ms 10516 KB Output is correct
13 Correct 92 ms 10512 KB Output is correct
14 Correct 114 ms 11008 KB Output is correct
15 Correct 161 ms 10940 KB Output is correct
16 Correct 83 ms 10332 KB Output is correct
17 Correct 100 ms 10436 KB Output is correct
18 Correct 122 ms 10644 KB Output is correct
19 Correct 156 ms 11284 KB Output is correct
20 Correct 157 ms 11192 KB Output is correct
21 Correct 161 ms 11212 KB Output is correct
22 Correct 175 ms 11976 KB Output is correct
23 Incorrect 171 ms 10972 KB Output isn't correct
24 Halted 0 ms 0 KB -