結果
| 問題 |
No.1881 Everything is the same...
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2022-03-18 07:57:15 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,148 bytes |
| コンパイル時間 | 3,491 ms |
| コンパイル使用メモリ | 94,016 KB |
| 実行使用メモリ | 67,864 KB |
| 最終ジャッジ日時 | 2024-10-02 13:33:04 |
| 合計ジャッジ時間 | 10,517 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 14 WA * 6 RE * 32 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.TreeMap;
class Main {
public static void main(String[] args) {
new Main().run();
}
int MAX=(int)1e4+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));
}
}
}
HashMap<Integer, ArrayList<Integer>> cyclic_group(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);
}
}
}
return decode;
}
void normalize(int[][] key) {
for (int i=0;i<key.length;++i) Arrays.sort(key[i]);
Arrays.sort(key, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
for (int i=0;i<o1.length;++i) if (o1[i]!=o2[i]) return Integer.compare(o1[i], o2[i]);
return 0;
}
});
}
int[][] compressed_state(int n) {
var decode=cyclic_group(n);
int[][] key=new int[bits][bits];
int size=0;
for (var entryset : decode.entrySet()) {
for (int i=0;i<entryset.getValue().size();++i) {
key[size][i]=entryset.getValue().get(i);
}
++size;
}
normalize(key);
return key;
}
int count(int n) {
var decode=cyclic_group(n);
int g=0;
int[][] key=new int[bits][bits];
int size=0;
for (var entryset : decode.entrySet()) {
for (int i=0;i<entryset.getValue().size();++i) {
key[size][i]=entryset.getValue().get(i);
}
++size;
}
normalize(key);
set.put(key, -1);
return g;
}
TreeMap<int[][], Integer> set=new TreeMap<>(new Comparator<int[][]>() {
@Override
public int compare(int[][] o1, int[][] o2) {
for (int i=0;i<o1.length;++i) {
for (int j=0;j<o1[i].length;++j) {
if (o1[i][j] != o2[i][j]) return Integer.compare(o1[i][j], o2[i][j]);
}
}
return 0;
}
});
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;
}
int bits=6;
int grundy(int a) {
return grundy(compressed_state(a));
}
int grundy(int[][] a) {
if (set.containsKey(a)) return set.get(a);
boolean[] vis=new boolean[17];
int[][] na=new int[bits][bits];
dfs(a, na, vis, 0, false);
int g=0;
while (vis[g]) ++g;
set.put(a, g);
return g;
}
int cnt=0;
void dfs(int[][] a, int[][] na, boolean[] vis, int pos, boolean less) {
if (pos <= a.length*a[0].length-1) {
int pi=pos/a[0].length;
int pj=pos%a[0].length;
for (int i= pj == 0 ? 0 : a[pi][pj-1];i<=a[pi][pj];++i) {
na[pi][pj]=i;
dfs(a, na, vis, pos+1, less | i < a[pi][pj]);
}
} else {
if (!less) return;
int[][] key=na.clone();
normalize(key);
vis[grundy(key)]=true;
++cnt;
}
}
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();
}
}