Submission #6903535
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; import java.math.BigInteger; public class Main implements Runnable { static int mod = 1000000007; public static void main(String[] args) { new Thread(null, new Main(), "", 1024 * 1024 * 1024).start(); } public void run() { PrintWriter out = new PrintWriter(System.out); FastScanner sc = new FastScanner(); int n = sc.nextInt(); Complex[] a = new Complex[n]; Complex[] b = new Complex[n]; for(int i=0;i<n;i++){ int ai = sc.nextInt(); int bi = sc.nextInt(); a[i] = new Complex(ai,0); b[i] = new Complex(bi,0); } Complex[] ans = FastFourierTransform.multiply(a, b); out.println(0); for(int i=0;i<2*n-1;i++){ out.println(Math.round(ans[i].real)); } out.flush(); } static void test(int[] a){ for(int i=0;i<a.length-1;i++){ System.out.print(a[i]); System.out.print(" "); } System.out.println(a[a.length-1]); } static void test(double[] a){ for(int i=0;i<a.length-1;i++){ System.out.print(a[i]); System.out.print(" "); } System.out.println(a[a.length-1]); } } class FastFourierTransform { static Complex[] dft(Complex[] f, int n){ Complex[] nf = new Complex[n]; for(int i=0;i<f.length;i++){ nf[i] = f[i]; } for(int i=f.length;i<n;i++){ nf[i] = new Complex(0,0); } return fft(nf,n,false); } static Complex[] invdft(Complex[] f, int n){ Complex[] nf = new Complex[n]; for(int i=0;i<f.length;i++){ nf[i] = f[i]; } for(int i=f.length;i<n;i++){ nf[i] = new Complex(0,0); } Complex[] ans = fft(nf,n,true); for(int i=0;i<n;i++){ ans[i] = ans[i].divide(n); } return ans; } static Complex[] multiply(Complex[] g, Complex[] h){ int n = up2Pow(g.length + h.length + 1); Complex[] gg = dft(g,n); Complex[] hh = dft(h,n); Complex[] ff = new Complex[n]; for(int i=0;i<n;i++){ ff[i] = gg[i].multiply(hh[i]); } return invdft(ff,n); } static long[] multiply(long[] a, long[] b){ Complex[] x = new Complex[a.length]; Complex[] y = new Complex[b.length]; for(int i=0;i<a.length;i++){ x[i] = new Complex(a[i],0); } for(int i=0;i<b.length;i++){ y[i] = new Complex(b[i],0); } Complex[] tmp = FastFourierTransform.multiply(x, y); long[] ans = new long[a.length + b.length - 1]; for(int i=0;i<a.length + b.length - 1;i++){ ans[i] = Math.round(tmp[i].real); } return ans; } //nは2冪 static Complex[] fft(Complex[] f, int n, boolean inv){ if(n == 1){ return f; } int m = n/2; Complex[] f0 = new Complex[m]; for(int i=0;i<m;i++){ f0[i] = f[2*i]; } f0 = fft(f0,m,inv); Complex[] f1 = new Complex[m]; for(int i=0;i<m;i++){ f1[i] = f[2*i+1]; } f1 = fft(f1,m,inv); Complex zeta = new Complex(Math.cos(2*Math.PI/n),Math.sin(2*Math.PI/n)); if(inv){ zeta = zeta.conjugate(); } Complex pow_zeta = new Complex(1,0); for(int i=0;i<n;i++){ f[i] = f0[i%m].sum(pow_zeta.multiply(f1[i%m])); pow_zeta = pow_zeta.multiply(zeta); } return f; } //n以上の最小の2ベキ static int up2Pow(int n){ if(n <= 0){ return 0; } if ((n&(n-1)) == 0){ //このときはn自身が2ベキ return n; } int ret = 1; while(n > 0){ ret<<=1; n>>=1; } return ret; } } class Complex { double real; double img; public Complex(double real, double img){ this.real = real; this.img = img; } Complex sum(Complex y){ return new Complex(this.real+y.real, this.img+y.img); } Complex multiply(Complex y){ return new Complex(this.real*y.real - this.img*y.img, this.real*y.img + this.img*y.real); } Complex conjugate(){ return new Complex(this.real, -this.img); } Complex divide(double y){ return new Complex(this.real/y, this.img/y); } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public int[] nextintArray(int n){ int[] a = new int[n]; for(int i=0;i<n;i++){ a[i] = nextInt(); } return a; } public long[] nextlongArray(int n){ long[] a = new long[n]; for(int i=0;i<n;i++){ a[i] = nextLong(); } return a; } public Integer[] nextIntegerArray(int n){ Integer[] a = new Integer[n]; for(int i=0;i<n;i++){ a[i] = nextInt(); } return a; } public int[][] nextintMatrix(int h, int w){ int[][] mat = new int[h][w]; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ mat[i][j] = nextInt(); } } return mat; } public double nextDouble() { return Double.parseDouble(next()); } }
Submission Info
Submission Time | |
---|---|
Task | A - 深さ優先探索 |
User | warachia |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 6799 Byte |
Status | WA |
Exec Time | 82 ms |
Memory | 25428 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt |
All | 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_min_01.txt | WA | 71 ms | 21460 KB |
00_min_02.txt | WA | 72 ms | 23508 KB |
00_min_03.txt | WA | 72 ms | 25428 KB |
00_min_04.txt | WA | 73 ms | 19156 KB |
00_min_05.txt | WA | 74 ms | 21332 KB |
00_min_06.txt | WA | 71 ms | 22868 KB |
00_min_07.txt | WA | 71 ms | 23508 KB |
00_min_08.txt | WA | 71 ms | 20820 KB |
00_sample_01.txt | WA | 71 ms | 20948 KB |
00_sample_02.txt | WA | 79 ms | 23252 KB |
00_sample_03.txt | WA | 74 ms | 23380 KB |
00_sample_04.txt | WA | 71 ms | 20180 KB |
00_sample_05.txt | WA | 70 ms | 23508 KB |
01_rnd_00.txt | WA | 71 ms | 22868 KB |
01_rnd_01.txt | WA | 72 ms | 21332 KB |
01_rnd_02.txt | WA | 71 ms | 23508 KB |
01_rnd_03.txt | WA | 70 ms | 21460 KB |
01_rnd_04.txt | WA | 72 ms | 23380 KB |
01_rnd_05.txt | WA | 72 ms | 23508 KB |
01_rnd_06.txt | WA | 70 ms | 20692 KB |
01_rnd_07.txt | WA | 73 ms | 21076 KB |
01_rnd_08.txt | WA | 72 ms | 21204 KB |
01_rnd_09.txt | WA | 73 ms | 21456 KB |
01_rnd_10.txt | WA | 70 ms | 18004 KB |
01_rnd_11.txt | WA | 72 ms | 21716 KB |
01_rnd_12.txt | WA | 73 ms | 21076 KB |
01_rnd_13.txt | WA | 73 ms | 25300 KB |
01_rnd_14.txt | WA | 72 ms | 23508 KB |
01_rnd_15.txt | WA | 71 ms | 21460 KB |
01_rnd_16.txt | WA | 71 ms | 22612 KB |
01_rnd_17.txt | WA | 72 ms | 22868 KB |
01_rnd_18.txt | WA | 82 ms | 23380 KB |
01_rnd_19.txt | WA | 71 ms | 23508 KB |
02_rndhard_00.txt | WA | 72 ms | 21972 KB |
02_rndhard_01.txt | WA | 72 ms | 21332 KB |
02_rndhard_02.txt | WA | 70 ms | 21460 KB |
02_rndhard_03.txt | WA | 73 ms | 19028 KB |
02_rndhard_04.txt | WA | 71 ms | 20052 KB |
02_rndhard_05.txt | WA | 72 ms | 20436 KB |
02_rndhard_06.txt | WA | 72 ms | 21076 KB |
02_rndhard_07.txt | WA | 72 ms | 24276 KB |
02_rndhard_08.txt | WA | 71 ms | 23380 KB |
02_rndhard_09.txt | WA | 72 ms | 21460 KB |
02_rndhard_10.txt | WA | 71 ms | 20948 KB |
02_rndhard_11.txt | WA | 73 ms | 23124 KB |
02_rndhard_12.txt | WA | 72 ms | 20564 KB |
02_rndhard_13.txt | WA | 72 ms | 21332 KB |
02_rndhard_14.txt | WA | 73 ms | 20948 KB |
02_rndhard_15.txt | WA | 73 ms | 21332 KB |
02_rndhard_16.txt | WA | 72 ms | 23380 KB |
02_rndhard_17.txt | WA | 71 ms | 19796 KB |
02_rndhard_18.txt | WA | 72 ms | 21076 KB |
02_rndhard_19.txt | WA | 71 ms | 20564 KB |
02_rndhard_20.txt | WA | 71 ms | 21332 KB |
02_rndhard_21.txt | WA | 73 ms | 23252 KB |
02_rndhard_22.txt | WA | 72 ms | 20052 KB |
02_rndhard_23.txt | WA | 73 ms | 23252 KB |
02_rndhard_24.txt | WA | 73 ms | 21716 KB |
02_rndhard_25.txt | WA | 71 ms | 20564 KB |
02_rndhard_26.txt | WA | 81 ms | 23508 KB |
02_rndhard_27.txt | WA | 72 ms | 19668 KB |
02_rndhard_28.txt | WA | 73 ms | 22356 KB |
02_rndhard_29.txt | WA | 74 ms | 21588 KB |
02_rndhard_30.txt | WA | 71 ms | 19796 KB |
02_rndhard_31.txt | WA | 73 ms | 22868 KB |
02_rndhard_32.txt | WA | 72 ms | 20308 KB |
02_rndhard_33.txt | WA | 71 ms | 22484 KB |
02_rndhard_34.txt | WA | 72 ms | 23508 KB |
02_rndhard_35.txt | WA | 71 ms | 22740 KB |
02_rndhard_36.txt | WA | 72 ms | 23508 KB |
02_rndhard_37.txt | WA | 73 ms | 20948 KB |
02_rndhard_38.txt | WA | 81 ms | 23764 KB |
02_rndhard_39.txt | WA | 73 ms | 21456 KB |
03_rndhardsmall_00.txt | WA | 72 ms | 21460 KB |
03_rndhardsmall_01.txt | WA | 72 ms | 23508 KB |
03_rndhardsmall_02.txt | WA | 71 ms | 19668 KB |
03_rndhardsmall_03.txt | WA | 73 ms | 23376 KB |
03_rndhardsmall_04.txt | WA | 72 ms | 25300 KB |
03_rndhardsmall_05.txt | WA | 73 ms | 20948 KB |
03_rndhardsmall_06.txt | WA | 82 ms | 23252 KB |
03_rndhardsmall_07.txt | WA | 71 ms | 23508 KB |
03_rndhardsmall_08.txt | WA | 73 ms | 22100 KB |
03_rndhardsmall_09.txt | WA | 73 ms | 21332 KB |