Submission #1036830


Source Code Expand

// package atcoder.other2016.codefestival2016.round3;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    private static final int INF = 10000000;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int[] a = in.nextInts(n);
        char[] s = in.nextToken().toCharArray();

        int[] base = new int[n];
        int ok = 1;
        int ng = n+1;
        while (ng - ok > 1) {
            int med = (ng+ok)/2;
            for (int i = 0; i < n ; i++) {
                base[i] = a[i] >= med ? 1 : 0;
            }
            if (solve(base, s) == 1) {
                ok = med;
            } else {
                ng = med;
            }
        }

        out.println(ok);
        out.flush();
    }

    private static int solve(int[] base, char[] s) {
        int n = base.length;
        int sum = 0;
        for (int i = 0; i < n ; i++) {
            sum += base[i];
        }
        if (sum == 0 || sum == n) {
            return sum == 0 ? 0 : 1;
        }



        Queue<Segment>[] onezero = new Queue[2];
        for (int i = 0; i < 2 ; i++) {
            onezero[i] = new PriorityQueue<>();
        }
        TreeSet<Segment> tree = new TreeSet<>((a, b) -> a.left - b.left);

        Segment head = null;
        Segment tail = null;
        for (int i = 0; i < n ; ) {
            int j = i;
            while (j < n && base[i] == base[j]) {
                j++;
            }
            int fr = i == 0 ? -INF : i;
            int to = j == n ? INF : j-1;
            Segment seg = new Segment(fr, to, base[i]);
            onezero[base[i]].add(seg);
            tree.add(seg);
            if (fr == -INF) {
                head = seg;
            } else if (to == INF) {
                tail = seg;
            }
            i = j;
        }

        int plus = 0;
        int minus = 0;

        int diff = 0;
        for (int i = 0; i < s.length ; i++) {
            int my, ot;
            if (s[i] == 'M') {
                diff++;
                plus++;
                my = 0;
                ot = 1;
            } else {
                diff--;
                minus++;
                my = 1;
                ot = 0;
            }

            while (onezero[my].size() >= 1) {
                Segment seg = onezero[my].peek();
                if (!seg.available) {
                    onezero[my].poll();
                    continue;
                }
                int[] tl = seg.eval(plus, minus);
                if (tl[0] > tl[1]) {
                    onezero[my].poll();
                    Segment L = tree.lower(seg);
                    Segment R = tree.higher(seg);
                    seg.available = false;
                    L.available = false;
                    R.available = false;
                    tree.remove(seg);
                    tree.remove(L);
                    tree.remove(R);

                    Segment newSeg = new Segment(L.left, R.right, L.value);
                    newSeg.cnt = L.cnt + R.cnt;
                    if (newSeg.value == 1) {
                        newSeg.cnt += diff;
                    } else {
                        newSeg.cnt -= diff;
                    }

                    tree.add(newSeg);
                    onezero[ot].add(newSeg);
                } else {
                    break;
                }
            }
        }

        for (Segment t : tree) {
            int[] fin = t.eval(plus, minus);
            if (fin[0] <= 0 && 0 <= fin[1]) {
                return t.value;
            }
        }
        throw new RuntimeException("arien");
    }

    static class Segment implements Comparable<Segment> {
        int left;
        int right;
        int value;
        int cnt;
        boolean available;

        public Segment(int fr, int to, int v) {
            left = fr;
            right = to;
            value = v;
            cnt = to-fr+1;
            available = true;
        }

        @Override
        public int compareTo(Segment o) {
            return cnt - o.cnt;
        }

        public int[] eval(int plus, int minus) {
            int tl = left;
            int tr = right;
            if (value == 0) {
                tl -= minus;
                tr -= plus;
            } else {
                tl -= plus;
                tr -= minus;
            }
            return new int[]{tl, tr};
        }
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int[] nextInts(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        private int[][] nextIntTable(int n, int m) {
            int[][] ret = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextInt();
                }
            }
            return ret;
        }

        private long[] nextLongs(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextLong();
            }
            return ret;
        }

        private long[][] nextLongTable(int n, int m) {
            long[][] ret = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextLong();
                }
            }
            return ret;
        }

        private double[] nextDoubles(int n) {
            double[] ret = new double[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextDouble();
            }
            return ret;
        }

        private int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            if ('a' <= c && c <= 'z') {
                return (char) c;
            }
            if ('A' <= c && c <= 'Z') {
                return (char) c;
            }
            throw new InputMismatchException();
        }

        public String nextToken() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}

Submission Info

Submission Time
Task B - Compression
User hamadu
Language Java8 (OpenJDK 1.8.0)
Score 1400
Code Size 9103 Byte
Status AC
Exec Time 1484 ms
Memory 71232 KB

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 400 / 400 800 / 800 200 / 200
Status
AC × 4
AC × 13
AC × 13
AC × 49
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt
subtask1 sample_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 2_1.txt, 2_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_15.txt, subtask_3_16.txt, subtask_3_17.txt, subtask_3_18.txt, subtask_3_19.txt, subtask_3_2.txt, subtask_3_20.txt, subtask_3_21.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
Case Name Status Exec Time Memory
2_1.txt AC 229 ms 14804 KB
2_2.txt AC 196 ms 13768 KB
sample_1.txt AC 195 ms 13900 KB
sample_2.txt AC 198 ms 13764 KB
sample_3.txt AC 188 ms 13632 KB
sample_4.txt AC 199 ms 13764 KB
subtask_1.2_1.txt AC 187 ms 13392 KB
subtask_1.2_2.txt AC 196 ms 13764 KB
subtask_1_1.txt AC 1019 ms 47424 KB
subtask_1_10.txt AC 712 ms 60052 KB
subtask_1_2.txt AC 740 ms 56236 KB
subtask_1_3.txt AC 921 ms 47512 KB
subtask_1_4.txt AC 876 ms 48704 KB
subtask_1_5.txt AC 351 ms 22644 KB
subtask_1_6.txt AC 733 ms 52356 KB
subtask_1_7.txt AC 199 ms 13892 KB
subtask_1_8.txt AC 1006 ms 45116 KB
subtask_1_9.txt AC 706 ms 53300 KB
subtask_2_1.txt AC 889 ms 58508 KB
subtask_2_10.txt AC 824 ms 67956 KB
subtask_2_2.txt AC 641 ms 57080 KB
subtask_2_3.txt AC 1267 ms 71232 KB
subtask_2_4.txt AC 711 ms 65524 KB
subtask_2_5.txt AC 195 ms 13640 KB
subtask_2_6.txt AC 187 ms 13768 KB
subtask_2_7.txt AC 188 ms 13772 KB
subtask_2_8.txt AC 1184 ms 70304 KB
subtask_2_9.txt AC 391 ms 31820 KB
subtask_3_1.txt AC 1357 ms 68412 KB
subtask_3_10.txt AC 1312 ms 63788 KB
subtask_3_11.txt AC 1484 ms 64072 KB
subtask_3_12.txt AC 715 ms 52552 KB
subtask_3_13.txt AC 818 ms 51368 KB
subtask_3_14.txt AC 885 ms 46532 KB
subtask_3_15.txt AC 743 ms 48964 KB
subtask_3_16.txt AC 703 ms 51156 KB
subtask_3_17.txt AC 683 ms 49636 KB
subtask_3_18.txt AC 789 ms 53244 KB
subtask_3_19.txt AC 703 ms 41728 KB
subtask_3_2.txt AC 1123 ms 58892 KB
subtask_3_20.txt AC 702 ms 52808 KB
subtask_3_21.txt AC 1026 ms 45028 KB
subtask_3_3.txt AC 438 ms 32312 KB
subtask_3_4.txt AC 1275 ms 66760 KB
subtask_3_5.txt AC 1263 ms 65068 KB
subtask_3_6.txt AC 1304 ms 65980 KB
subtask_3_7.txt AC 1129 ms 56008 KB
subtask_3_8.txt AC 1381 ms 63180 KB
subtask_3_9.txt AC 820 ms 57140 KB