結果
問題 | No.387 ハンコ |
ユーザー |
|
提出日時 | 2016-07-02 16:58:25 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,525 ms / 5,000 ms |
コード長 | 1,858 bytes |
コンパイル時間 | 4,879 ms |
コンパイル使用メモリ | 77,236 KB |
実行使用メモリ | 63,324 KB |
最終ジャッジ日時 | 2024-10-12 01:04:34 |
合計ジャッジ時間 | 26,356 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 |
ソースコード
package yukicoder;import java.util.Arrays;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];}}// 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) {System.out.println("ODD");} else {System.out.println("EVEN");}}}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;}}