Submission #254781

#	Time	Username	Problem	Language	Result	Execution time	Memory
254781		model_code	Mixture (BOI20_mixture)	Java	100 / 100	1448 ms	55436 KiB

Mixture

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

public class Mixture {
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str;
        String[] params;

        str = br.readLine();
        params = str.split(" ");
        long S = Integer.parseInt(params[0]);
        long P = Integer.parseInt(params[1]);
        long G = Integer.parseInt(params[2]);

        str = br.readLine();
        int N = Integer.parseInt(str);

        ArrayList<Vector> data = new ArrayList<>(N);
        TreeSet<Vector> set = new TreeSet<>();
        long amountOfDots = 0;
        long amountOfLines = 0;
        long amountOfEmptyPies = 1;

        for (int i = 0; i < N; i++) {
            str = br.readLine();
            params = str.split(" ");
            if (params[0].equals("A")) {
                long s = Integer.parseInt(params[1]);
                long p = Integer.parseInt(params[2]);
                long g = Integer.parseInt(params[3]);

                long x = s * (S + P + G) - S * (s + p + g);
                long y = p * (S + P + G) - P * (s + p + g);

                if ((x == 0) && (y == 0)) {
                    data.add(new Vector(0, 0));
                    amountOfDots++;
                } else {
                    long mult = s + p + g;
                    Vector cur = new Vector(mult * x, mult * y);
                    data.add(cur);

                    Vector existing = set.ceiling(cur);
                    if ((existing != null) && (existing.compareTo(cur) == 0)) {
                        existing.setCount(existing.getCount() + 1);
                    } else {
                        Vector same = set.ceiling(cur);
                        Vector opposite = set.ceiling(cur.negate());
                        if (((same == null) || (same.compareTo(cur) != 0))
                                && ((opposite != null) && (opposite.compareTo(cur.negate()) == 0))) {
                            amountOfLines++;
                        }

                        if (set.size() >= 2) {
                            Vector prev = Optional.ofNullable(set.lower(cur)).orElse(set.last());
                            Vector next = Optional.ofNullable(set.higher(cur)).orElse(set.first());

                            if ((crossProductResult(prev, next) > 0)
                                    && (crossProductResult(prev, cur) <= 0)
                                    && (crossProductResult(cur, next) <= 0)) {
                                amountOfEmptyPies = 0;
                            }
                        } else {
                            amountOfEmptyPies = 1;
                        }

                        set.add(cur);
                    }
                }
            } else {
                int ind = Integer.parseInt(params[1]);
                Vector cur = data.get(ind - 1);

                if ((cur.getPart() == -1)) {
                    amountOfDots--;
                } else {
                    Vector existing = set.ceiling(cur);
                    if (existing.getCount() > 1) {
                        existing.setCount(existing.getCount() - 1);
                    } else {
                        set.remove(cur);

                        Vector same = set.ceiling(cur);
                        Vector opposite = set.ceiling(cur.negate());
                        if (((same == null) || (same.compareTo(cur) != 0))
                                && ((opposite != null) && (opposite.compareTo(cur.negate()) == 0))) {
                            amountOfLines--;
                        }

                        if (set.size() >= 2) {
                            Vector prev = Optional.ofNullable(set.lower(cur)).orElse(set.last());
                            Vector next = Optional.ofNullable(set.higher(cur)).orElse(set.first());

                            if (crossProductResult(prev, next) > 0) {
                                amountOfEmptyPies = 1;
                            }
                        } else {
                            amountOfEmptyPies = 1;
                        }
                    }
                }
            }
            if (amountOfDots > 0) {
                bw.write("1\n");
            } else if (amountOfLines > 0) {
                bw.write("2\n");
            } else if (amountOfEmptyPies == 0) {
                bw.write("3\n");
            } else {
                bw.write("0\n");
            }
        }
        bw.close();
    }

    private static class Vector implements Comparable<Vector> {

        private final long x, y;

        // -1 = 0-vector
        // 0 = [0; pi)
        // 1 = [pi; 2pi)
        private final int part;
        private int count = 1;

        public Vector(long x, long y) {
            this.x = x;
            this.y = y;

            if (x == 0) {
                if (y > 0) {
                    this.part = 0;
                } else if (y < 0) {
                    this.part = 1;
                } else {
                    this.part = -1;
                }
            } else if (x > 0) {
                this.part = 0;
            } else {
                this.part = 1;
            }
        }

        public long getX() {
            return x;
        }

        public long getY() {
            return y;
        }

        public Integer getPart() {
            return part;
        }

        public Vector negate() {
            return new Vector(-x, -y);
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        @Override
        public int compareTo(Vector o) {
            int result = this.getPart().compareTo(o.getPart());
            if (result == 0) {
                result = crossProductResult(this, o);
            }
            return result;
        }
    }

    private static int crossProductResult(Vector a, Vector b) {
        /*
        return BigInteger.valueOf(a.getX()).multiply(BigInteger.valueOf(b.getY()))
                .compareTo(BigInteger.valueOf(a.getY()).multiply(BigInteger.valueOf(b.getX())));
         */
        long MOD = 1L << 31;

        long p0 = (b.y % MOD) * (a.x % MOD);
        long p1 = (b.y % MOD) * (a.x / MOD) + (a.x % MOD) * (b.y / MOD);
        long p2 = (a.x / MOD) * (b.y / MOD);
        long p3 = 0;
        p1 += p0 / MOD;
        p0 %= MOD;
        p2 += p1 / MOD;
        p1 %= MOD;
        p3 += p2 / MOD;
        p2 %= MOD;

        long q0 = (b.x % MOD) * (a.y % MOD);
        long q1 = (b.x % MOD) * (a.y / MOD) + (a.y % MOD) * (b.x / MOD);
        long q2 = (a.y / MOD) * (b.x / MOD);
        long q3 = 0;
        q1 += q0 / MOD;
        q0 %= MOD;
        q2 += q1 / MOD;
        q1 %= MOD;
        q3 += q2 / MOD;
        q2 %= MOD;

        if (p3 < q3) {
            return -1;
        } else if (p3 > q3) {
            return 1;
        } else {
            if (p2 < q2) {
                return -1;
            } else if (p2 > q2) {
                return 1;
            } else {
                if (p1 < q1) {
                    return -1;
                } else if (p1 > q1) {
                    return 1;
                } else {
                    if (p0 < q0) {
                        return -1;
                    } else if (p0 > q0) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        }
    }

}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40