結果

問題 No.387 ハンコ
ユーザー 37zigen37zigen
提出日時 2016-07-02 02:03:48
言語 Java21
(openjdk 21)
結果
MLE  
実行時間 -
コード長 4,349 bytes
コンパイル時間 2,475 ms
コンパイル使用メモリ 83,620 KB
実行使用メモリ 755,708 KB
最終ジャッジ日時 2024-04-20 06:47:43
合計ジャッジ時間 12,596 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 MLE -
testcase_08 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.Scanner;

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][N];
		int[] b = new int[N];
		for (int i = 0; i < N; i++) {
			a[sc.nextInt() - 1][i]++;
		}
		for (int i = 0; i < N; i++) {
			b[i] = sc.nextInt();
		}
		int[][] c = new int[N][2 * N];
		for (int i = 0; i < N; i++) {
			c[i] = convolute(a[i], b);
		}
		
		for (int i = 0; i < 2 * N-1; i++) {
			long sum=0;
			for(int j=0;j<N;j++){
				if(c[j][i]>0)sum++;
			}
//			System.out.println(sum);
			if (sum % 2 == 0) {
				System.out.println("EVEN");
			} else {
				System.out.println("ODD");
			}
		}

	}

	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 };
	}

}
0