Submission #894848
Source Code Expand
import java.io.*; import java.util.*; public class Main { BufferedReader br; PrintWriter out; StringTokenizer st; boolean eof; void solve() throws IOException { int n = nextInt(); // arrays int m = nextInt(); // numbers in each array int q = nextInt(); int[] a = new int[q]; for (int i = q - 1; i >= 0; i--) { a[i] = nextInt() - 1; } TreeSet<Integer>[] sets = new TreeSet[m]; for (int i = 0; i < m; i++) { sets[i] = new TreeSet<>(); } for (int i = 0; i < q; i++) { sets[a[i]].add(i); } boolean[] used = new boolean[m]; int[] ptrs = new int[n]; Arrays.fill(ptrs, -1); int curPos = 0; int lastProper = -1; outer: while (true) { // ? while (curPos < q && used[a[curPos]]) { curPos++; } if (curPos == q) { // huh? out.println("Yes"); return; } int num = a[curPos]; used[num] = true; int prev = -1; for (int i = 0; i < n; i++) { Integer newPtr = sets[num].higher(Math.max(prev, ptrs[i])); if (newPtr == null) { lastProper = num; break outer; } sets[num].remove(newPtr); ptrs[i] = newPtr; prev = newPtr; } } List<Integer> rest = new ArrayList<>(); rest.add(lastProper); for (int i = curPos; i < q; i++) { if (!used[a[i]]) { rest.add(a[i]); used[a[i]] = true; } } for (int i = 0; i < m; i++) { if (!used[i]) { rest.add(i); } } for (int i = 0; i < rest.size() - 1; i++) { if (rest.get(i) > rest.get(i + 1)) { out.println("No"); return; } } out.println("Yes"); } Main() throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); solve(); out.close(); } public static void main(String[] args) throws IOException { new Main(); } String nextToken() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (Exception e) { eof = true; return null; } } return st.nextToken(); } String nextString() { try { return br.readLine(); } catch (IOException e) { eof = true; return null; } } int nextInt() throws IOException { return Integer.parseInt(nextToken()); } long nextLong() throws IOException { return Long.parseLong(nextToken()); } double nextDouble() throws IOException { return Double.parseDouble(nextToken()); } }
Submission Info
Submission Time | |
---|---|
Task | E - LRU Puzzle |
User | mmaxio |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1200 |
Code Size | 2546 Byte |
Status | AC |
Exec Time | 514 ms |
Memory | 36184 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1200 / 1200 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 105 ms | 8400 KB |
0_01.txt | AC | 97 ms | 8144 KB |
0_02.txt | AC | 97 ms | 8144 KB |
0_03.txt | AC | 98 ms | 8276 KB |
1_00.txt | AC | 98 ms | 8404 KB |
1_01.txt | AC | 96 ms | 8276 KB |
1_02.txt | AC | 320 ms | 36184 KB |
1_03.txt | AC | 322 ms | 35760 KB |
1_04.txt | AC | 336 ms | 35716 KB |
1_05.txt | AC | 340 ms | 35632 KB |
1_06.txt | AC | 254 ms | 32288 KB |
1_07.txt | AC | 255 ms | 31660 KB |
1_08.txt | AC | 260 ms | 31936 KB |
1_09.txt | AC | 269 ms | 31808 KB |
1_10.txt | AC | 271 ms | 32556 KB |
1_11.txt | AC | 266 ms | 32416 KB |
1_12.txt | AC | 260 ms | 32476 KB |
1_13.txt | AC | 237 ms | 32380 KB |
1_14.txt | AC | 260 ms | 32020 KB |
1_15.txt | AC | 262 ms | 31984 KB |
1_16.txt | AC | 270 ms | 32000 KB |
1_17.txt | AC | 250 ms | 32020 KB |
1_18.txt | AC | 267 ms | 32000 KB |
1_19.txt | AC | 277 ms | 32072 KB |
1_20.txt | AC | 258 ms | 32284 KB |
1_21.txt | AC | 249 ms | 32116 KB |
1_22.txt | AC | 285 ms | 33220 KB |
1_23.txt | AC | 290 ms | 32940 KB |
1_24.txt | AC | 274 ms | 32952 KB |
1_25.txt | AC | 288 ms | 32984 KB |
1_26.txt | AC | 245 ms | 24736 KB |
1_27.txt | AC | 231 ms | 24624 KB |
1_28.txt | AC | 514 ms | 24908 KB |
1_29.txt | AC | 256 ms | 25416 KB |
1_30.txt | AC | 297 ms | 34524 KB |
1_31.txt | AC | 317 ms | 34788 KB |
1_32.txt | AC | 297 ms | 34332 KB |
1_33.txt | AC | 285 ms | 31804 KB |
1_34.txt | AC | 271 ms | 32692 KB |
1_35.txt | AC | 303 ms | 33568 KB |
1_36.txt | AC | 273 ms | 33992 KB |
1_37.txt | AC | 237 ms | 32636 KB |
1_38.txt | AC | 288 ms | 34208 KB |
1_39.txt | AC | 278 ms | 32536 KB |
1_40.txt | AC | 294 ms | 32904 KB |
1_41.txt | AC | 275 ms | 31940 KB |
1_42.txt | AC | 257 ms | 24904 KB |
1_43.txt | AC | 264 ms | 25140 KB |
1_44.txt | AC | 236 ms | 24888 KB |
1_45.txt | AC | 232 ms | 24832 KB |
1_46.txt | AC | 267 ms | 34348 KB |
1_47.txt | AC | 292 ms | 34216 KB |
1_48.txt | AC | 310 ms | 34484 KB |
1_49.txt | AC | 301 ms | 32160 KB |
1_50.txt | AC | 248 ms | 24860 KB |
1_51.txt | AC | 262 ms | 24612 KB |
1_52.txt | AC | 253 ms | 25576 KB |
1_53.txt | AC | 261 ms | 25244 KB |
1_54.txt | AC | 298 ms | 34588 KB |
1_55.txt | AC | 286 ms | 35316 KB |
1_56.txt | AC | 307 ms | 34640 KB |
1_57.txt | AC | 264 ms | 31960 KB |
1_58.txt | AC | 239 ms | 24668 KB |
1_59.txt | AC | 229 ms | 24468 KB |
1_60.txt | AC | 227 ms | 24628 KB |
1_61.txt | AC | 236 ms | 24780 KB |
1_62.txt | AC | 299 ms | 34748 KB |
1_63.txt | AC | 282 ms | 35844 KB |
1_64.txt | AC | 276 ms | 34920 KB |
1_65.txt | AC | 291 ms | 32120 KB |
1_66.txt | AC | 288 ms | 24744 KB |
1_67.txt | AC | 273 ms | 24352 KB |
1_68.txt | AC | 283 ms | 24540 KB |
1_69.txt | AC | 271 ms | 25568 KB |
1_70.txt | AC | 292 ms | 35884 KB |
1_71.txt | AC | 316 ms | 32144 KB |