Submission #1036824


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;
                    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 1200
Code Size 8914 Byte
Status WA
Exec Time 1346 ms
Memory 68612 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 0 / 200
Status
AC × 4
AC × 13
AC × 13
AC × 42
WA × 7
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 218 ms 14028 KB
2_2.txt AC 184 ms 13512 KB
sample_1.txt AC 196 ms 13900 KB
sample_2.txt AC 189 ms 14028 KB
sample_3.txt AC 181 ms 13760 KB
sample_4.txt AC 195 ms 14024 KB
subtask_1.2_1.txt AC 188 ms 13392 KB
subtask_1.2_2.txt AC 180 ms 13764 KB
subtask_1_1.txt AC 918 ms 54980 KB
subtask_1_10.txt AC 706 ms 39976 KB
subtask_1_2.txt AC 701 ms 57460 KB
subtask_1_3.txt AC 895 ms 54904 KB
subtask_1_4.txt AC 657 ms 48572 KB
subtask_1_5.txt AC 339 ms 22024 KB
subtask_1_6.txt AC 920 ms 45216 KB
subtask_1_7.txt AC 190 ms 13900 KB
subtask_1_8.txt AC 846 ms 42704 KB
subtask_1_9.txt AC 751 ms 53356 KB
subtask_2_1.txt AC 808 ms 68612 KB
subtask_2_10.txt AC 954 ms 62440 KB
subtask_2_2.txt AC 623 ms 56756 KB
subtask_2_3.txt AC 1242 ms 68464 KB
subtask_2_4.txt AC 734 ms 57884 KB
subtask_2_5.txt AC 197 ms 13896 KB
subtask_2_6.txt AC 181 ms 13508 KB
subtask_2_7.txt AC 189 ms 13768 KB
subtask_2_8.txt AC 963 ms 62048 KB
subtask_2_9.txt AC 377 ms 36492 KB
subtask_3_1.txt WA 1342 ms 65744 KB
subtask_3_10.txt AC 1076 ms 58252 KB
subtask_3_11.txt WA 1315 ms 67360 KB
subtask_3_12.txt AC 824 ms 48812 KB
subtask_3_13.txt AC 835 ms 51340 KB
subtask_3_14.txt AC 1049 ms 54748 KB
subtask_3_15.txt AC 685 ms 47864 KB
subtask_3_16.txt AC 649 ms 41536 KB
subtask_3_17.txt AC 946 ms 50796 KB
subtask_3_18.txt AC 1168 ms 52968 KB
subtask_3_19.txt AC 679 ms 52424 KB
subtask_3_2.txt WA 1346 ms 66248 KB
subtask_3_20.txt AC 840 ms 42584 KB
subtask_3_21.txt AC 699 ms 50808 KB
subtask_3_3.txt WA 412 ms 31656 KB
subtask_3_4.txt WA 1162 ms 61280 KB
subtask_3_5.txt WA 1285 ms 62820 KB
subtask_3_6.txt AC 1218 ms 66296 KB
subtask_3_7.txt AC 1265 ms 60632 KB
subtask_3_8.txt WA 1235 ms 58744 KB
subtask_3_9.txt AC 879 ms 46936 KB