結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー | uwi |
提出日時 | 2015-05-09 00:32:26 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 456 ms / 7,000 ms |
コード長 | 5,778 bytes |
コンパイル時間 | 4,172 ms |
コンパイル使用メモリ | 78,076 KB |
実行使用メモリ | 73,108 KB |
最終ジャッジ日時 | 2023-09-19 09:08:22 |
合計ジャッジ時間 | 12,479 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
49,252 KB |
testcase_01 | AC | 44 ms
49,288 KB |
testcase_02 | AC | 45 ms
49,340 KB |
testcase_03 | AC | 44 ms
49,260 KB |
testcase_04 | AC | 44 ms
49,388 KB |
testcase_05 | AC | 45 ms
49,280 KB |
testcase_06 | AC | 70 ms
51,124 KB |
testcase_07 | AC | 67 ms
50,192 KB |
testcase_08 | AC | 87 ms
52,276 KB |
testcase_09 | AC | 88 ms
52,644 KB |
testcase_10 | AC | 46 ms
49,412 KB |
testcase_11 | AC | 49 ms
49,440 KB |
testcase_12 | AC | 104 ms
53,240 KB |
testcase_13 | AC | 96 ms
54,760 KB |
testcase_14 | AC | 81 ms
51,468 KB |
testcase_15 | AC | 108 ms
53,320 KB |
testcase_16 | AC | 96 ms
52,572 KB |
testcase_17 | AC | 328 ms
66,548 KB |
testcase_18 | AC | 322 ms
66,296 KB |
testcase_19 | AC | 330 ms
65,612 KB |
testcase_20 | AC | 296 ms
65,820 KB |
testcase_21 | AC | 346 ms
66,184 KB |
testcase_22 | AC | 336 ms
66,192 KB |
testcase_23 | AC | 333 ms
66,264 KB |
testcase_24 | AC | 455 ms
70,800 KB |
testcase_25 | AC | 456 ms
73,108 KB |
testcase_26 | AC | 442 ms
70,264 KB |
testcase_27 | AC | 410 ms
67,312 KB |
testcase_28 | AC | 397 ms
69,684 KB |
testcase_29 | AC | 418 ms
70,760 KB |
testcase_30 | AC | 424 ms
70,264 KB |
ソースコード
package contest; 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 Q440 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { int L = ni(), M = ni(), N = ni(); int[] a = new int[N+1]; for(int i = 0;i < L;i++)a[ni()] = 1; int[] b = new int[N+1]; for(int i = 0;i < M;i++)b[N-ni()] = 1; int Q = ni(); long[] ab = convolute(a, b); for(int i = 0;i < Q;i++){ out.println(ab[N+i]); } } public static long[] convolute(int[] a, int[] b) { int m = Integer.highestOneBit(Math.max(Math.max(a.length, b.length)-1, 1))<<2; double[][] fa = fft(a, m, false); double[][] fb = a == b ? fa : fft(b, m, false); for(int i = 0;i < m;i++){ double nfa0 = fa[0][i]*fb[0][i]-fa[1][i]*fb[1][i]; double nfa1 = fa[0][i]*fb[1][i]+fa[1][i]*fb[0][i]; fa[0][i] = nfa0; fa[1][i] = nfa1; } fft(fa[0], fa[1], true); long[] ret = new long[m]; for(int i = 0;i < m;i++){ ret[i] = Math.round(fa[0][i]); } return ret; } public static double[][] fft(int[] srcRe, int n, boolean inverse) { int m = srcRe.length; double[] dstRe = new double[n]; double[] dstIm = new double[n]; for(int i = 0;i < m;i++){ dstRe[i] = srcRe[i]; } int h = Integer.numberOfTrailingZeros(n); for(int i = 0;i < n;i++){ int rev = Integer.reverse(i)>>>32-h; if(i < rev){ double d = dstRe[i]; dstRe[i] = dstRe[rev]; dstRe[rev] = d; } } for(int s = 2;s <= n;s <<= 1){ int nt = s >>> 1; double theta = inverse ? -2*Math.PI/s : 2*Math.PI/s; double wRe = Math.cos(theta); double wIm = Math.sin(theta); for(int j = 0; j < n;j += s){ double wr = 1, wi = 0; for(int t = j;t < j+nt;t++){ int jp = t + nt; double re = dstRe[jp]*wr - dstIm[jp]*wi; double im = dstRe[jp]*wi + dstIm[jp]*wr; dstRe[jp] = dstRe[t] - re; dstIm[jp] = dstIm[t] - im; dstRe[t] += re; dstIm[t] += im; double nwre = wr * wRe - wi * wIm; double nwim = wr * wIm + wi * wRe; wr = nwre; wi = nwim; } } } if(inverse){ for(int i = 0;i < n;i++){ dstRe[i] /= n; dstIm[i] /= n; } } return new double[][]{dstRe, dstIm}; } public static void fft(double[] re, double[] im, boolean inverse) { int n = re.length; int h = Integer.numberOfTrailingZeros(n); for(int i = 0;i < n;i++){ int rev = Integer.reverse(i)>>>32-h; if(i < rev){ double d = re[i]; re[i] = re[rev]; re[rev] = d; d = im[i]; im[i] = im[rev]; im[rev] = d; } } for(int s = 2;s <= n;s <<= 1){ int nt = s >>> 1; double theta = inverse ? -2*Math.PI/s : 2*Math.PI/s; double wRe = Math.cos(theta); double wIm = Math.sin(theta); for(int j = 0; j < n;j += s){ double wr = 1, wi = 0; for(int t = j;t < j+nt;t++){ int jp = t + nt; double lre = re[jp]*wr - im[jp]*wi; double lim = re[jp]*wi + im[jp]*wr; re[jp] = re[t] - lre; im[jp] = im[t] - lim; re[t] += lre; im[t] += lim; double nwre = wr * wRe - wi * wIm; double nwim = wr * wIm + wi * wRe; wr = nwre; wi = nwim; } } } if(inverse){ for(int i = 0;i < n;i++){ re[i] /= n; im[i] /= n; } } } 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"); } public static void main(String[] args) throws Exception { new Q440().run(); } private byte[] inbuf = new byte[1024]; private 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 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[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private int ni() { int num = 0, 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 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)); } }