Submission #2837036
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.util.NoSuchElementException; public class Main { static PrintWriter out; static InputReader ir; static boolean debug = false; static void solve() { char[] a = ir.next().toCharArray(); int n = a.length; int[][][] dp = new int[n + 1][26][2]; for (int i = 0; i < 26; i++) dp[n][i] = new int[] { i, 1 }; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < 26; j++) for (int k = 0; k < 2; k++) dp[i][j][k] = dp[i + 1][j][k]; int cur = a[i] - 'a'; int mi = 2 * n; for (int j = 0; j < 26; j++) mi = Math.min(mi, dp[i + 1][j][1]); for (int j = 0; j < 26; j++) { if (dp[i + 1][j][1] == mi) { dp[i][cur] = new int[] { j, dp[i + 1][j][1] + 1 }; break; } } } int mi = 2 * n, cur = -1; ; for (int i = 0; i < 26; i++) mi = Math.min(mi, dp[0][i][1]); for (int i = 0; i < 26; i++) if (dp[0][i][1] == mi) { cur = i; break; } tr(dp[0]); String ret = Character.toString((char) ('a' + cur)); for (int i = 0; i < n; i++) { if (dp[i][cur][0] == dp[i + 1][cur][0] && dp[i][cur][1] == dp[i + 1][cur][1]) continue; ret += Character.toString((char) ('a' + dp[i][cur][0])); cur = dp[i][cur][0]; } out.println(ret); } public static void main(String[] args) { ir = new InputReader(System.in); out = new PrintWriter(System.out); solve(); out.flush(); } static class InputReader { private InputStream in; private byte[] buffer = new byte[1024]; private int curbuf; private int lenbuf; public InputReader(InputStream in) { this.in = in; this.curbuf = this.lenbuf = 0; } public boolean hasNextByte() { if (curbuf >= lenbuf) { curbuf = 0; try { lenbuf = in.read(buffer); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return false; } return true; } private int readByte() { if (hasNextByte()) return buffer[curbuf++]; else return -1; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private void skip() { while (hasNextByte() && isSpaceChar(buffer[curbuf])) curbuf++; } public boolean hasNext() { skip(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } public char[][] nextCharMap(int n, int m) { char[][] map = new char[n][m]; for (int i = 0; i < n; i++) map[i] = next().toCharArray(); return map; } } static void tr(Object... o) { if (debug) out.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | E - Don't Be a Subsequence |
User | holeguma |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 4332 Byte |
Status | MLE |
Exec Time | 1908 ms |
Memory | 322264 KB |
Compile Error
./Main.java:44: warning: non-varargs call of varargs method with inexact argument type for last parameter; tr(dp[0]); ^ cast to Object for a varargs call cast to Object[] for a non-varargs call and to suppress this warning 1 warning
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
1.txt | AC | 69 ms | 20820 KB |
10.txt | AC | 1688 ms | 232720 KB |
11.txt | AC | 1741 ms | 232452 KB |
12.txt | AC | 1719 ms | 226676 KB |
13.txt | AC | 1675 ms | 227048 KB |
14.txt | AC | 1694 ms | 227876 KB |
15.txt | AC | 1716 ms | 227796 KB |
16.txt | AC | 1690 ms | 228740 KB |
17.txt | MLE | 1747 ms | 254592 KB |
18.txt | MLE | 1741 ms | 253656 KB |
19.txt | MLE | 1804 ms | 278128 KB |
2.txt | AC | 75 ms | 18772 KB |
20.txt | MLE | 1863 ms | 297316 KB |
21.txt | MLE | 1890 ms | 322264 KB |
22.txt | MLE | 1865 ms | 319404 KB |
23.txt | MLE | 1908 ms | 319672 KB |
24.txt | AC | 1695 ms | 228868 KB |
25.txt | AC | 1696 ms | 228164 KB |
26.txt | AC | 1670 ms | 228180 KB |
27.txt | AC | 1694 ms | 226432 KB |
28.txt | AC | 1771 ms | 227208 KB |
29.txt | AC | 1658 ms | 229788 KB |
3.txt | AC | 111 ms | 30356 KB |
30.txt | AC | 1706 ms | 223232 KB |
4.txt | AC | 109 ms | 25892 KB |
5.txt | AC | 836 ms | 137120 KB |
6.txt | AC | 822 ms | 137836 KB |
7.txt | AC | 1718 ms | 229492 KB |
8.txt | AC | 1714 ms | 228148 KB |
9.txt | AC | 1705 ms | 230916 KB |
sample1.txt | AC | 68 ms | 18004 KB |
sample2.txt | AC | 115 ms | 18132 KB |
sample3.txt | AC | 67 ms | 17620 KB |