結果
問題 | No.941 商とあまり |
ユーザー | uwi |
提出日時 | 2019-12-04 04:31:13 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,086 ms / 2,000 ms |
コード長 | 6,965 bytes |
コンパイル時間 | 5,166 ms |
コンパイル使用メモリ | 81,240 KB |
実行使用メモリ | 94,324 KB |
最終ジャッジ日時 | 2023-08-19 08:06:28 |
合計ジャッジ時間 | 43,453 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge9 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 283 ms
59,084 KB |
testcase_01 | AC | 169 ms
56,056 KB |
testcase_02 | AC | 167 ms
56,188 KB |
testcase_03 | AC | 193 ms
55,944 KB |
testcase_04 | AC | 182 ms
55,840 KB |
testcase_05 | AC | 173 ms
55,980 KB |
testcase_06 | AC | 164 ms
56,464 KB |
testcase_07 | AC | 265 ms
59,380 KB |
testcase_08 | AC | 255 ms
59,232 KB |
testcase_09 | AC | 294 ms
61,224 KB |
testcase_10 | AC | 253 ms
56,484 KB |
testcase_11 | AC | 268 ms
58,732 KB |
testcase_12 | AC | 200 ms
56,388 KB |
testcase_13 | AC | 295 ms
58,904 KB |
testcase_14 | AC | 255 ms
59,340 KB |
testcase_15 | AC | 294 ms
58,392 KB |
testcase_16 | AC | 292 ms
60,592 KB |
testcase_17 | AC | 302 ms
61,084 KB |
testcase_18 | AC | 314 ms
63,032 KB |
testcase_19 | AC | 454 ms
70,444 KB |
testcase_20 | AC | 156 ms
56,224 KB |
testcase_21 | AC | 175 ms
55,836 KB |
testcase_22 | AC | 152 ms
56,512 KB |
testcase_23 | AC | 41 ms
49,252 KB |
testcase_24 | AC | 40 ms
47,236 KB |
testcase_25 | AC | 40 ms
49,132 KB |
testcase_26 | AC | 263 ms
59,004 KB |
testcase_27 | AC | 277 ms
59,032 KB |
testcase_28 | AC | 265 ms
58,796 KB |
testcase_29 | AC | 294 ms
60,976 KB |
testcase_30 | AC | 295 ms
60,800 KB |
testcase_31 | AC | 246 ms
59,352 KB |
testcase_32 | AC | 198 ms
55,780 KB |
testcase_33 | AC | 184 ms
56,088 KB |
testcase_34 | AC | 332 ms
63,020 KB |
testcase_35 | AC | 312 ms
60,444 KB |
testcase_36 | AC | 253 ms
58,960 KB |
testcase_37 | AC | 253 ms
59,088 KB |
testcase_38 | AC | 276 ms
59,004 KB |
testcase_39 | AC | 256 ms
58,956 KB |
testcase_40 | AC | 163 ms
55,804 KB |
testcase_41 | AC | 168 ms
56,300 KB |
testcase_42 | AC | 159 ms
55,296 KB |
testcase_43 | AC | 264 ms
59,060 KB |
testcase_44 | AC | 261 ms
59,248 KB |
testcase_45 | AC | 374 ms
64,600 KB |
testcase_46 | AC | 306 ms
62,524 KB |
testcase_47 | AC | 267 ms
59,300 KB |
testcase_48 | AC | 169 ms
55,948 KB |
testcase_49 | AC | 270 ms
58,772 KB |
testcase_50 | AC | 262 ms
58,792 KB |
testcase_51 | AC | 254 ms
59,028 KB |
testcase_52 | AC | 243 ms
59,076 KB |
testcase_53 | AC | 257 ms
58,896 KB |
testcase_54 | AC | 428 ms
70,460 KB |
testcase_55 | AC | 435 ms
70,256 KB |
testcase_56 | AC | 403 ms
70,344 KB |
testcase_57 | AC | 1,086 ms
94,324 KB |
testcase_58 | AC | 699 ms
80,316 KB |
testcase_59 | AC | 273 ms
58,884 KB |
testcase_60 | AC | 291 ms
59,180 KB |
testcase_61 | AC | 207 ms
55,704 KB |
testcase_62 | AC | 311 ms
59,720 KB |
testcase_63 | AC | 296 ms
58,832 KB |
testcase_64 | AC | 265 ms
59,000 KB |
testcase_65 | AC | 318 ms
59,156 KB |
testcase_66 | AC | 256 ms
58,900 KB |
testcase_67 | AC | 340 ms
59,084 KB |
testcase_68 | AC | 240 ms
59,060 KB |
testcase_69 | AC | 332 ms
58,952 KB |
testcase_70 | AC | 348 ms
58,988 KB |
testcase_71 | AC | 326 ms
58,928 KB |
testcase_72 | AC | 294 ms
59,060 KB |
testcase_73 | AC | 350 ms
59,192 KB |
testcase_74 | AC | 351 ms
60,836 KB |
testcase_75 | AC | 302 ms
60,776 KB |
testcase_76 | AC | 291 ms
59,092 KB |
testcase_77 | AC | 294 ms
59,304 KB |
testcase_78 | AC | 411 ms
60,896 KB |
testcase_79 | AC | 360 ms
60,864 KB |
testcase_80 | AC | 383 ms
61,152 KB |
testcase_81 | AC | 358 ms
61,072 KB |
testcase_82 | AC | 383 ms
60,924 KB |
testcase_83 | AC | 301 ms
61,276 KB |
testcase_84 | AC | 332 ms
60,960 KB |
testcase_85 | AC | 396 ms
62,464 KB |
testcase_86 | AC | 333 ms
60,932 KB |
testcase_87 | AC | 327 ms
60,968 KB |
testcase_88 | AC | 324 ms
60,704 KB |
testcase_89 | AC | 496 ms
64,708 KB |
testcase_90 | AC | 445 ms
62,972 KB |
testcase_91 | AC | 462 ms
62,788 KB |
testcase_92 | AC | 489 ms
65,244 KB |
testcase_93 | AC | 441 ms
63,468 KB |
testcase_94 | AC | 399 ms
64,800 KB |
testcase_95 | AC | 451 ms
65,432 KB |
testcase_96 | AC | 365 ms
62,736 KB |
testcase_97 | AC | 358 ms
62,716 KB |
testcase_98 | AC | 164 ms
55,460 KB |
testcase_99 | AC | 365 ms
63,096 KB |
testcase_100 | AC | 444 ms
64,872 KB |
testcase_101 | AC | 169 ms
55,492 KB |
testcase_102 | AC | 165 ms
55,436 KB |
testcase_103 | AC | 514 ms
72,660 KB |
testcase_104 | AC | 40 ms
49,360 KB |
testcase_105 | AC | 40 ms
49,444 KB |
testcase_106 | AC | 41 ms
49,820 KB |
testcase_107 | AC | 42 ms
49,380 KB |
testcase_108 | AC | 42 ms
49,648 KB |
testcase_109 | AC | 41 ms
49,384 KB |
ソースコード
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Adv19D4_3 { InputStream is; PrintWriter out; // String INPUT = "2 50\r\n" + // "4 5\r\n" + // ""; String INPUT = ""; // String INPUT = "4 500000 65 66 67 68"; // String INPUT = "6 500000 1 2 3 4 5 6"; // String INPUT = "4 500000 3 4 5 6"; // String INPUT = "18 500000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"; // String INPUT = "10 500000 1 1 1 2 2 3 4 5 6 7"; // String INPUT = "6 500000 5 7 11 13 17 23"; long[][] bit; long ct = 0; void paint(long[] a, int s, int X, int K) { if(K < 32) { for(int i = s;i>>>6 == s>>>6;i+=K) { a[i>>>6] |= 1L<<i; } for(int j = (s>>>6)+1;j <= X>>>6;j++) { // s+ak >= j*64 // a = (j*64-s+k-1)/k long first = (j*64-s+K-1)/K; long ss = s+first*K&63; a[j] |= bit[K][(int)ss]; } // for(int i = s;i <= X;i+=K) { // a[i>>>6] |= 1L<<i; // } }else { for(int i = s;i <= X;i+=K) { ct++; a[i>>>6] |= 1L<<i; } } } void solve() { int n = ni(), X = ni(); int[] a = na(n); double u = 1; for(int v : a) { u *= v+1; if(u-1 > X) { for(int i = 0;i < X;i++) { out.print(0); } out.println(); return; } } Arrays.sort(a); int[][] f = uniqcount(a); int[] fi = new int[f.length]; for(int i = 0;i < f.length;i++)fi[i] = f[i][1] + 1; Denom de = new Denom(fi); bit = new long[32][32]; for(int i = 1;i < 32;i++) { for(int j = 0;j < i;j++) { for(int k = j;k < 64;k+=i) { bit[i][j] |= 1L<<k; } } } long[][] dp = new long[de.all()][X/64+2]; for(int i = 0;i < de.all();i++) { for(int j = 0;j < f.length;j++) { if(de.in(i, j, 1)) { int ni = de.add(i, j, 1); if(i == 0) { dp[ni][f[j][0]>>>6] |= 1L<<f[j][0]; }else { int F = X; for(int w = 0;w < f.length;w++) { for(int k = f[w][1] - de.dec(i)[w] - (w == j ? 1 : 0);k > 0;k--) { F /= f[w][0]+1; } } F++; // tr(i, j, ni); int l = f[j][0]; // int ct = 0; long h = 0; for(int k = 1;(long)k*(l+1)+l <= X;k++) { if(dp[i][k>>>6]<<~k<0) { paint(dp[ni], k*(l+1)+l, F, k); // for(int m = k*(l+1)+l;m <= X;m+=k) { // dp[ni][m>>>6] |= 1L<<m; // } if(k%l < 64) { if(h<<~(k%l)<0) { continue; } h |= 1L<<(k%l); } paint(dp[ni], k*(l+1)+l, F, l); // for(int m = k*(l+1)+l;m <= X;m+=l) { //// ct++; // dp[ni][m>>>6] |= 1L<<m; // } } } // tr(i, j, ni, ct); } } } } for(int i = 1;i <= X;i++) { out.print(dp[de.all()-1][i>>>6]<<~i<0 ? 1 : 0); } out.println(); } public static int[] getind(int[][] a, int ind) { int[] b = new int[a.length]; for(int i = 0;i < a.length;i++)b[i] = a[i][ind]; return b; } public static class Denom { int[] a; int[] ia; Denom(int... ia) { this.ia = ia; int n = ia.length; a = new int[n+1]; a[0] = 1; for(int i = 0;i < n;i++){ a[i+1] = a[i] * ia[i]; } } int[] dec(int code) { int[] ret = new int[a.length-1]; for(int i = 0;i < a.length-1;i++) { ret[i] = code % a[i+1] / a[i]; } return ret; } int ind(int... x) { assert x.length == ia.length; int ret = 0; for(int i = 0;i < x.length;i++){ ret += x[i] * a[i]; } return ret; } boolean in(int code, int which, int plus) { int v = v(code, which); return 0 <= v + plus && v + plus < ia[which]; } int v(int code, int which) { return code / a[which] % ia[which]; } int add(int code, int which, int plus) { return code + a[which] * plus; } int update(int code, int which, int val) { return code + (-code / a[which] % ia[which] + val) * a[which]; } int all() { return a[a.length-1]; } } public static int[][] uniqcount(int[] a) { int n = a.length; int p = 0; int[][] b = new int[n][]; for(int i = 0;i < n;i++){ if(i == 0 || a[i] != a[i-1])b[p++] = new int[]{a[i], 0}; b[p-1][1]++; } return Arrays.copyOf(b, p); } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new Adv19D4_3().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }