結果
問題 | No.1881 Everything is the same... |
ユーザー | 37zigen |
提出日時 | 2022-01-18 02:33:53 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,162 bytes |
コンパイル時間 | 3,317 ms |
コンパイル使用メモリ | 97,508 KB |
実行使用メモリ | 78,368 KB |
最終ジャッジ日時 | 2024-04-10 11:31:35 |
合計ジャッジ時間 | 22,362 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 328 ms
76,840 KB |
testcase_07 | AC | 231 ms
67,540 KB |
testcase_08 | AC | 245 ms
67,068 KB |
testcase_09 | AC | 231 ms
67,360 KB |
testcase_10 | WA | - |
testcase_11 | AC | 305 ms
71,928 KB |
testcase_12 | AC | 373 ms
78,148 KB |
testcase_13 | AC | 406 ms
78,144 KB |
testcase_14 | AC | 406 ms
78,188 KB |
testcase_15 | AC | 383 ms
78,072 KB |
testcase_16 | AC | 379 ms
78,252 KB |
testcase_17 | AC | 378 ms
77,620 KB |
testcase_18 | AC | 360 ms
78,064 KB |
testcase_19 | AC | 407 ms
77,896 KB |
testcase_20 | AC | 410 ms
77,824 KB |
testcase_21 | AC | 409 ms
78,200 KB |
testcase_22 | AC | 361 ms
77,784 KB |
testcase_23 | WA | - |
testcase_24 | AC | 407 ms
77,912 KB |
testcase_25 | AC | 366 ms
76,860 KB |
testcase_26 | AC | 387 ms
77,568 KB |
testcase_27 | AC | 399 ms
77,948 KB |
testcase_28 | AC | 364 ms
77,300 KB |
testcase_29 | AC | 370 ms
78,048 KB |
testcase_30 | WA | - |
testcase_31 | AC | 372 ms
77,928 KB |
testcase_32 | WA | - |
testcase_33 | AC | 383 ms
78,056 KB |
testcase_34 | AC | 394 ms
78,068 KB |
testcase_35 | AC | 407 ms
78,368 KB |
testcase_36 | AC | 374 ms
77,904 KB |
testcase_37 | AC | 370 ms
77,108 KB |
testcase_38 | AC | 405 ms
78,044 KB |
testcase_39 | WA | - |
testcase_40 | AC | 394 ms
77,784 KB |
testcase_41 | AC | 394 ms
77,832 KB |
testcase_42 | AC | 249 ms
67,028 KB |
testcase_43 | AC | 255 ms
67,056 KB |
testcase_44 | AC | 252 ms
66,992 KB |
testcase_45 | AC | 238 ms
67,472 KB |
testcase_46 | AC | 291 ms
67,016 KB |
testcase_47 | AC | 255 ms
67,460 KB |
testcase_48 | AC | 233 ms
66,964 KB |
testcase_49 | AC | 276 ms
67,480 KB |
testcase_50 | AC | 251 ms
67,000 KB |
testcase_51 | AC | 262 ms
67,264 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.NoSuchElementException; class Main { public static void main(String[] args) { new Main().run(); } int MAX=(int)1e5+1; boolean[] isPrime=new boolean[MAX]; ArrayList<Integer> primes=new ArrayList<>(); ArrayList<List<Integer>>[] pe=new ArrayList[MAX]; { for (int i=0;i<pe.length;++i) pe[i]=new ArrayList<>(); Arrays.fill(isPrime, true); isPrime[0]=isPrime[1]=false; for (int i=2;i<MAX;++i) { if (!isPrime[i]) continue; primes.add(i); for (int j=i;j<MAX;j+=i) { if (j>i) isPrime[j]=false; int e=0; int v=j; while (v%i==0) { v/=i; ++e; } pe[j].add(List.of(i, e)); } } } int grundy(int n) { HashMap<Integer, ArrayList<Integer>> decode=new HashMap<>(); for (var pair : pe[n]) { int p=pair.get(0); int e=pair.get(1); if (p != 2) { if (e >= 2) decode.computeIfAbsent(p, key -> new ArrayList<>()).add(e-1); for (var pair2 : pe[p-1]) { int p2=pair2.get(0); int e2=pair2.get(1); decode.computeIfAbsent(p2, key -> new ArrayList<>()).add(e2); } } else { if (e == 2) { decode.computeIfAbsent(p, key -> new ArrayList<>()).add(1); } else if (e >= 3){ decode.computeIfAbsent(p, key -> new ArrayList<>()).add(e-2); decode.computeIfAbsent(p, key -> new ArrayList<>()).add(1); } } } int g=0; for (var entryset : decode.entrySet()) { int[] key=new int[bits]; for (int i=0;i<entryset.getValue().size();++i) { key[i]=entryset.getValue().get(i); } Arrays.sort(key); g+=grundy.get(hash(key)); } return g; } long pow(long a, long n) { if (n==0) return 1; return pow(a*a, n/2) * (n%2==1? a : 1) ; } long hash(int[] a) { long ret=1; for (int i=0;i<a.length;++i) { ret*=pow(primes.get(i), a[a.length-1-i]); } return ret; } HashMap<Long, Integer> grundy=new HashMap<>(); int bits=16; { dfs1(new int[bits], bits, bits-1); } void dfs1(int[] a, int res, int pos) { if (pos >= 0) { int upper = pos+1 != a.length ? Math.min(res, a[pos+1]) : res; for (int nxt=0; nxt <= upper;++nxt) { a[pos]=nxt; dfs1(a, res-nxt, pos-1); } } else { int[] b=new int[a.length]; boolean[] vis=new boolean[17]; dfs2(a, b, vis, 0, false); int g=0; while (vis[g]) ++g; grundy.put(hash(a), g); } } void dfs2(int[] a, int[] b, boolean[] vis, int pos, boolean less) { if (pos < a.length) { for (int i= pos == 0 ? 0 : a[pos-1];i<=a[pos];++i) { b[pos]=i; dfs2(a, b, vis, pos+1, less | i < a[pos]); } } else { long key=hash(b); if (!less && grundy.containsKey(key)) throw new AssertionError();//ハッシュが衝突 if (less) vis[grundy.get(key)]=true; } } void run() { solve(); } void solve() { FastScanner sc=new FastScanner(); int N=sc.nextInt(); int[] A=new int[N]; int g=0; for (int i=0;i<N;++i) { A[i]=sc.nextInt(); g^=grundy(A[i]); } System.out.println(g==0?"X":"Y"); } static void tr(Object...objects) { System.out.println(Arrays.deepToString(objects)); } } 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;} private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;} public boolean hasNext() { skipUnprintable(); 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() { return (int)nextLong(); } }