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 |
|
|
|
|
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 |