結果

問題 No.387 ハンコ
ユーザー 37zigen37zigen
提出日時 2016-07-02 17:00:50
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,431 ms / 5,000 ms
コード長 2,962 bytes
コンパイル時間 2,224 ms
コンパイル使用メモリ 78,764 KB
実行使用メモリ 66,624 KB
最終ジャッジ日時 2024-10-12 01:06:48
合計ジャッジ時間 13,989 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 982 ms
65,500 KB
testcase_01 AC 941 ms
65,396 KB
testcase_02 AC 1,395 ms
66,624 KB
testcase_03 AC 1,431 ms
65,376 KB
testcase_04 AC 488 ms
51,360 KB
testcase_05 AC 886 ms
54,844 KB
testcase_06 AC 1,083 ms
55,612 KB
testcase_07 AC 1,059 ms
65,020 KB
testcase_08 AC 1,076 ms
66,276 KB
権限があれば一括ダウンロードができます

ソースコード

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;
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];
		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[][] bucket = makeBucket(a, 100001);

		// stamp[i][j]:スタンプをiだけ左にシフトしたとき、64ビット区分でi番目の区分にはどのような数が入るか。
		long[][] stamp = new long[64][(N >>> 6) + 2];
		for (int i = 0; i < 64; i++) {
			for (int j = 0; j < N; j++) {
				stamp[i][(i + j) >>> 6] |= (long) b[j] << (j + i);
			}
		}
		long[] ans = new long[((2 * N) >>> 6) + 10];
		for (int[] row : bucket) {
			long[] d = new long[(2 * N >>> 6) + 10];
			for (int x : row) {
				int lo = 63 & x;
				int hi = x >>> 6;
				for (int j = 0; j < ((N >>> 6) + 2) && j + hi < d.length; j++) {
					d[j + hi] |= stamp[lo][j];
				}
			}
			for (int i = 0; i < d.length; i++) {
				ans[i] ^= d[i];
			}
		}
		Printer pr=new Printer(System.out);
//		System.out.println(Long.toBinaryString(ans[0]));
		for (int i = 0; i < 2 * N - 1; i++) {
//			System.out.println(Long.toBinaryString(ans[i>>>6]));
			if (((ans[i >>> 6]) >> (i & 63) & 1) == 1) {
				pr.println("ODD");
			} else {
				pr.println("EVEN");
			}
		}
		pr.close();
	}

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

	int[][] makeBucket(int[] a, int sup) {
		int n = a.length;
		int[][] bucket = new int[sup + 1][];
		int[] bp = new int[sup + 1];
		for (int i = 0; i < n; i++) {
			bp[a[i]]++;
		}
		for (int i = 0; i < sup + 1; i++) {
			bucket[i] = new int[bp[i]];
		}
		for (int i = n - 1; i >= 0; i--) {
			bucket[a[i]][--bp[a[i]]] = i;
		}
		return bucket;
	}
	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