Submission #2526543
Source Code Expand
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { char[] cs; public static void main(String args[]) { new Main().run(); } void run() { FastReader sc = new FastReader(); cs = sc.next().toCharArray(); solve(); } void solve() { int[] used = new int[26]; List<Integer> list = new ArrayList<>(); List<List<Integer>> occurrences = new ArrayList<>(); for (int i = 0; i < 26; i++) { occurrences.add(new ArrayList<>()); } for (int i = cs.length - 1; i >= 0; i--) { occurrences.get(cs[i] - 'a').add(i); used[cs[i] - 'a']++; boolean flag = true; for (int j = 0; j < used.length; j++) { if (used[j] == 0) { flag = false; break; } } if (flag) { list.add(i); Arrays.fill(used, 0); } } Collections.sort(list); list.add(cs.length); for (int i = 0; i < occurrences.size(); i++) { Collections.sort(occurrences.get(i)); } //for (int i = 0; i < occurrences.get(0).size(); i++) { //System.out.print(" " + occurrences.get(0).get(i)); //} //System.out.println(); int index = 0; int currentPosition = 0; StringBuilder ans = new StringBuilder(); for (int i = 0; i < list.size(); i++) { //System.out.println(i + " " + currentPosition); for (int j = 0; j < used.length; j++) { int nextOccurrence = lower_bound(occurrences.get(j), currentPosition); if (nextOccurrence == occurrences.get(j).size()) { ans.append((char)(j + 'a')); break; } //System.out.println(index); //System.out.println(list.get(index) + " " + occurrences.get(j).get(nextOccurrence) + " " + list.get(index + 1)); if (index < list.size() - 1) { if (list.get(index) < occurrences.get(j).get(nextOccurrence) && occurrences.get(j).get(nextOccurrence) < list.get(index + 1)) { ans.append((char) (j + 'a')); currentPosition = occurrences.get(j).get(nextOccurrence) + 1; index++; break; } } } //System.out.println(ans); } System.out.println(ans); } static int lower_bound(List<Integer> arr, int key) { int low = 0; int high = arr.size() - 1; while (high - low >= 0) { int mid = (low + high) / 2; if (key <= arr.get(mid)) { high = mid - 1; } else { low = mid + 1; } } return low; } static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } }
Submission Info
Submission Time | |
---|---|
Task | E - Don't Be a Subsequence |
User | ynish |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 4363 Byte |
Status | WA |
Exec Time | 207 ms |
Memory | 34056 KB |
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 | 72 ms | 20692 KB |
10.txt | WA | 189 ms | 31236 KB |
11.txt | WA | 198 ms | 30076 KB |
12.txt | WA | 186 ms | 32408 KB |
13.txt | WA | 183 ms | 31876 KB |
14.txt | WA | 193 ms | 34056 KB |
15.txt | WA | 163 ms | 33796 KB |
16.txt | WA | 171 ms | 29568 KB |
17.txt | WA | 186 ms | 29924 KB |
18.txt | WA | 189 ms | 29548 KB |
19.txt | WA | 207 ms | 30100 KB |
2.txt | AC | 84 ms | 21076 KB |
20.txt | WA | 192 ms | 30152 KB |
21.txt | WA | 196 ms | 28480 KB |
22.txt | WA | 162 ms | 28240 KB |
23.txt | WA | 163 ms | 29480 KB |
24.txt | WA | 188 ms | 27976 KB |
25.txt | WA | 176 ms | 31012 KB |
26.txt | AC | 159 ms | 30156 KB |
27.txt | WA | 164 ms | 27856 KB |
28.txt | AC | 168 ms | 31824 KB |
29.txt | AC | 169 ms | 29536 KB |
3.txt | WA | 98 ms | 21076 KB |
30.txt | AC | 160 ms | 28392 KB |
4.txt | WA | 88 ms | 22100 KB |
5.txt | WA | 138 ms | 27960 KB |
6.txt | WA | 131 ms | 24032 KB |
7.txt | WA | 187 ms | 30264 KB |
8.txt | WA | 194 ms | 26756 KB |
9.txt | WA | 205 ms | 29364 KB |
sample1.txt | AC | 71 ms | 18388 KB |
sample2.txt | WA | 70 ms | 20820 KB |
sample3.txt | AC | 71 ms | 18388 KB |