結果

問題 No.387 ハンコ
コンテスト
ユーザー 37zigen
提出日時 2016-07-02 02:22:00
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 5,698 bytes
コンパイル時間 2,351 ms
コンパイル使用メモリ 80,232 KB
実行使用メモリ 196,652 KB
最終ジャッジ日時 2024-10-12 01:56:56
合計ジャッジ時間 15,032 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;

public class Main {
	public static void main(String[] args) {
		new Main().solver();
	}

	void solver() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		int[] b = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt() - 1;
		}
		for (int i = 0; i < N; i++) {
			b[i] = sc.nextInt();
		}
		int[] ret = new int[2 * N];
		int[] d = new int[N];
		int[] c = new int[2 * N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (a[j] == i)
					d[j] = 1;
				else
					d[j] = 0;
			}
			c = convolute(d, b);
//			tr(c);
			for (int j = 0; j < 2 * N - 1; j++) {
				if (c[j] > 0) {
					ret[j]++;
				}
			}
		}
		Printer pr = new Printer(System.out);
		for (int i = 0; i < 2 * N - 1; i++) {
			if (ret[i] % 2 == 0) {
				pr.println("EVEN");
			} else {
				pr.println("ODD");
			}
		}
		pr.close();

	}

	void tr(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	public static double[][] doFFT(double[] srcRe, double[] srcIm) {
		int n = srcRe.length;
		if (Integer.bitCount(n) != 1)
			return null;
		int[] rev = reverseBitOrder(n);

		double[] dstRe = new double[n];
		double[] dstIm = new double[n];

		for (int i = 0; i < n; i++) {
			dstRe[i] = srcRe[rev[i]];
			dstIm[i] = srcIm[rev[i]];
		}

		for (int s = 1; s <= n; s <<= 1) {
			int nt = s >>> 1;
			int bs = nt;

			double wRe = 1.0;
			double wIm = 0.0;
			double uRe = Math.cos(Math.PI / bs);
			double uIm = -Math.sin(Math.PI / bs);

			for (int t = 0; t < nt; t++) {
				for (int j = t; j < n; j += s) {
					int jp = j + bs;
					double re = dstRe[jp] * wRe - dstIm[jp] * wIm;
					double im = dstRe[jp] * wIm + dstIm[jp] * wRe;
					dstRe[jp] = dstRe[j] - re;
					dstIm[jp] = dstIm[j] - im;
					dstRe[j] += re;
					dstIm[j] += im;
				}
				double nwRe = wRe * uRe - wIm * uIm;
				double nwIm = wRe * uIm + wIm * uRe;
				wRe = nwRe;
				wIm = nwIm;
			}
		}
		return new double[][] { dstRe, dstIm };
	}

	protected static int[] reverseBitOrder(int n) {
		int[] ret = new int[n];
		ret[0] = 0;
		for (int i = 1, h = n >> 1; i < n; i <<= 1, h >>>= 1) {
			for (int j = 0; j < i; j++) {
				ret[j + i] = ret[j] + h;
			}
		}
		return ret;
	}

	public static int[] convolute(int[] a, int[] b) {
		int m = Integer.highestOneBit(a.length | b.length) << 2;
		prepareFFT(m);
		double[][] fa = doFFFT(a, m);
		double[][] fb = doFFFT(b, m);
		double[][] fced = new double[2][m];
		for (int i = 0; i < m; i++) {
			fced[0][i] = (fa[0][i] * fb[0][i] - fa[1][i] * fb[1][i]) / m;
			fced[1][i] = (fa[0][i] * fb[1][i] + fa[1][i] * fb[0][i]) / -m;
		}
		double[][] ced = doFFFT(fced[0], fced[1]);
		int[] ret = new int[m];
		for (int i = 0; i < m; i++) {
			ret[i] = (int) Math.round(ced[0][i]);
		}
		return ret;
	}

	static int[] rev;
	static double[] coss;

	public static void prepareFFT(int n) {
		rev = reverseBitOrder(n);
		coss = new double[n + 1];
		for (int i = 0; i <= n >>> 1; i++) {
			coss[n - i] = coss[i] = Math.cos(Math.PI * i / (n >>> 1));
		}
	}

	public static double[][] doFFFT(int[] srcRe, int n) {
		int m = srcRe.length;
		double[] dstRe = new double[n];
		double[] dstIm = new double[n];

		for (int i = 0; i < n; i++) {
			if (rev[i] < m) {
				dstRe[i] = srcRe[rev[i]];
			}
		}

		for (int s = 1; s <= n; s <<= 1) {
			int nt = s >>> 1;
			int bs = nt;

			for (int t = 0; t < nt; t++) {
				double wRe = coss[t * (n / s)];
				double wIm = coss[(n >>> 2) + t * (n / s)];
				for (int j = t; j < n; j += s) {
					int jp = j + bs;
					double re = dstRe[jp] * wRe - dstIm[jp] * wIm;
					double im = dstRe[jp] * wIm + dstIm[jp] * wRe;
					dstRe[jp] = dstRe[j] - re;
					dstIm[jp] = dstIm[j] - im;
					dstRe[j] += re;
					dstIm[j] += im;
				}
			}
		}
		return new double[][] { dstRe, dstIm };
	}

	public static double[][] doFFFT(double[] srcRe, double[] srcIm) {
		int n = srcRe.length;
		double[] dstRe = new double[n];
		double[] dstIm = new double[n];

		for (int i = 0; i < n; i++) {
			dstRe[i] = srcRe[rev[i]];
			dstIm[i] = srcIm[rev[i]];
		}

		for (int s = 2; s <= n; s <<= 1) {
			int nt = s >>> 1;
			int bs = nt;

			for (int t = 0; t < nt; t++) {
				double wRe = coss[t * (n / s)];
				double wIm = coss[(n >>> 2) + t * (n / s)];
				for (int j = t; j < n; j += s) {
					int jp = j + bs;
					double re = dstRe[jp] * wRe - dstIm[jp] * wIm;
					double im = dstRe[jp] * wIm + dstIm[jp] * wRe;
					dstRe[jp] = dstRe[j] - re;
					dstIm[jp] = dstIm[j] - im;
					dstRe[j] += re;
					dstIm[j] += im;
				}
			}
		}
		return new double[][] { dstRe, dstIm };
	}

	private static class Scanner {
		BufferedReader br;
		Iterator<String> it;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		String next() throws RuntimeException {
			try {
				if (it == null || !it.hasNext())
					it = Arrays.asList(br.readLine().split(" ")).iterator();
				return it.next();
			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		int nextInt() throws RuntimeException {
			return Integer.parseInt(next());
		}

		long nextLong() throws RuntimeException {
			return Long.parseLong(next());
		}

		double nextDouble() throws RuntimeException {
			return Double.parseDouble(next());
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}

}
0