Submission #895618
Source Code Expand
import java.io.*; import java.util.*; public class Main { FastScanner in; PrintWriter out; void solve() { int n = in.nextInt(); int m = in.nextInt(); int q = in.nextInt(); int[] a = new int[q]; for (int i = 0; i < q; i++) { a[i] = in.nextInt() - 1; } int[] pos = new int[m]; Arrays.fill(pos, -1); int nowPos = 0; int[] vals = new int[m]; int[] num = new int[m + 1]; num[0] = n; for (int i = q - 1; i >= 0; i--) { int id = a[i]; if (pos[id] == -1) { vals[nowPos] = id; pos[id] = nowPos; nowPos++; } if (num[pos[id]] > 0) { num[pos[id]]--; num[pos[id] + 1]++; } } for (int i = 0; i < m; i++) { if (num[i] !=0) { boolean[] all = new boolean[m]; Arrays.fill(all, true); for (int j = 0; j < m; j++) { if (pos[j] != -1 && pos[j] < i) { all[j] = false; } } int it = 0; boolean ok = true; for (int j = i; j < nowPos; j++) { while (!all[it]) { it++; } if (it != vals[j]) { ok = false; break; } it++; } out.println(ok ? "Yes" : "No"); return; } } out.println("Yes"); } void run() { try { in = new FastScanner(new File("object.in")); out = new PrintWriter(new File("object.out")); solve(); out.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } } void runIO() { in = new FastScanner(System.in); out = new PrintWriter(System.out); solve(); out.close(); } class FastScanner { BufferedReader br; StringTokenizer st; public FastScanner(File f) { try { br = new BufferedReader(new FileReader(f)); } catch (FileNotFoundException e) { e.printStackTrace(); } } public FastScanner(InputStream f) { br = new BufferedReader(new InputStreamReader(f)); } String next() { while (st == null || !st.hasMoreTokens()) { String s = null; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } if (s == null) return null; st = new StringTokenizer(s); } return st.nextToken(); } boolean hasMoreTokens() { while (st == null || !st.hasMoreTokens()) { String s = null; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } if (s == null) return false; st = new StringTokenizer(s); } return true; } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } } public static void main(String[] args) { new Thread(null, new Runnable() { public void run() { new Main().runIO(); } }, "1", 1 << 26).start(); } }
Submission Info
Submission Time | |
---|---|
Task | E - LRU Puzzle |
User | qwerty787788 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1200 |
Code Size | 2885 Byte |
Status | AC |
Exec Time | 1103 ms |
Memory | 24344 KB |
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 | 99 ms | 8428 KB |
0_01.txt | AC | 97 ms | 8428 KB |
0_02.txt | AC | 100 ms | 8432 KB |
0_03.txt | AC | 97 ms | 8428 KB |
1_00.txt | AC | 98 ms | 8432 KB |
1_01.txt | AC | 98 ms | 8428 KB |
1_02.txt | AC | 194 ms | 18452 KB |
1_03.txt | AC | 189 ms | 18416 KB |
1_04.txt | AC | 184 ms | 18552 KB |
1_05.txt | AC | 187 ms | 18540 KB |
1_06.txt | AC | 209 ms | 24260 KB |
1_07.txt | AC | 211 ms | 24344 KB |
1_08.txt | AC | 203 ms | 23028 KB |
1_09.txt | AC | 220 ms | 23272 KB |
1_10.txt | AC | 196 ms | 22388 KB |
1_11.txt | AC | 200 ms | 22388 KB |
1_12.txt | AC | 209 ms | 23284 KB |
1_13.txt | AC | 214 ms | 23132 KB |
1_14.txt | AC | 199 ms | 22292 KB |
1_15.txt | AC | 205 ms | 22388 KB |
1_16.txt | AC | 187 ms | 22416 KB |
1_17.txt | AC | 204 ms | 22388 KB |
1_18.txt | AC | 206 ms | 23008 KB |
1_19.txt | AC | 189 ms | 22396 KB |
1_20.txt | AC | 211 ms | 23964 KB |
1_21.txt | AC | 195 ms | 23040 KB |
1_22.txt | AC | 198 ms | 22976 KB |
1_23.txt | AC | 202 ms | 22748 KB |
1_24.txt | AC | 221 ms | 22992 KB |
1_25.txt | AC | 207 ms | 22480 KB |
1_26.txt | AC | 560 ms | 19604 KB |
1_27.txt | AC | 190 ms | 18508 KB |
1_28.txt | AC | 194 ms | 18868 KB |
1_29.txt | AC | 205 ms | 19788 KB |
1_30.txt | AC | 198 ms | 19864 KB |
1_31.txt | AC | 216 ms | 19876 KB |
1_32.txt | AC | 199 ms | 19612 KB |
1_33.txt | AC | 1103 ms | 22760 KB |
1_34.txt | AC | 210 ms | 22900 KB |
1_35.txt | AC | 200 ms | 22144 KB |
1_36.txt | AC | 205 ms | 20780 KB |
1_37.txt | AC | 188 ms | 22264 KB |
1_38.txt | AC | 189 ms | 22688 KB |
1_39.txt | AC | 203 ms | 22796 KB |
1_40.txt | AC | 207 ms | 22828 KB |
1_41.txt | AC | 221 ms | 22988 KB |
1_42.txt | AC | 195 ms | 18604 KB |
1_43.txt | AC | 198 ms | 18716 KB |
1_44.txt | AC | 192 ms | 18580 KB |
1_45.txt | AC | 192 ms | 18480 KB |
1_46.txt | AC | 194 ms | 19340 KB |
1_47.txt | AC | 194 ms | 19488 KB |
1_48.txt | AC | 195 ms | 19364 KB |
1_49.txt | AC | 197 ms | 22892 KB |
1_50.txt | AC | 195 ms | 18840 KB |
1_51.txt | AC | 197 ms | 18568 KB |
1_52.txt | AC | 193 ms | 18992 KB |
1_53.txt | AC | 208 ms | 18864 KB |
1_54.txt | AC | 193 ms | 19656 KB |
1_55.txt | AC | 192 ms | 19148 KB |
1_56.txt | AC | 192 ms | 20368 KB |
1_57.txt | AC | 200 ms | 22812 KB |
1_58.txt | AC | 196 ms | 19340 KB |
1_59.txt | AC | 184 ms | 18564 KB |
1_60.txt | AC | 182 ms | 18572 KB |
1_61.txt | AC | 193 ms | 19100 KB |
1_62.txt | AC | 187 ms | 18936 KB |
1_63.txt | AC | 193 ms | 18432 KB |
1_64.txt | AC | 187 ms | 18824 KB |
1_65.txt | AC | 209 ms | 22580 KB |
1_66.txt | AC | 180 ms | 17308 KB |
1_67.txt | AC | 171 ms | 17256 KB |
1_68.txt | AC | 183 ms | 17256 KB |
1_69.txt | AC | 183 ms | 17412 KB |
1_70.txt | AC | 185 ms | 18536 KB |
1_71.txt | AC | 221 ms | 22876 KB |