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