結果
| 問題 |
No.1881 Everything is the same...
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2022-03-18 09:24:29 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 910 ms / 2,000 ms |
| コード長 | 7,892 bytes |
| コンパイル時間 | 3,811 ms |
| コンパイル使用メモリ | 95,140 KB |
| 実行使用メモリ | 76,180 KB |
| 最終ジャッジ日時 | 2024-10-02 13:31:20 |
| 合計ジャッジ時間 | 35,039 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 52 |
ソースコード
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)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));
}
}
}
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=new int[bits][bits];
for (int i=0;i<bits;++i)for(int j=0;j<bits;++j) key[i][j]=na[i][j];
normalize(key);
int g=grundy(key);
vis[g]=true;
++cnt;
}
}
// 90 まで確かめた。
void run() {
solve();
// for (int i=1;i<=100;++i) {
// if (grundy(i) != new BruteForce().calc(i)) throw new AssertionError();
// else System.out.println("ok"+i+" grundy"+grundy(i));
// }
}
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 BruteForce {
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) {
if (o1[i] != o2[i]) return Integer.compare(o1[i], o2[i]);
}
return 0;
}
});
int calc(int n) {
DSU dsu=new DSU(n+1);
return grundy(n, dsu);
}
int grundy(int n, DSU dsu) {
if (set.containsKey(dsu.parent)) return set.get(dsu.parent);
boolean[] vis=new boolean[20];
for (int add=2;add<n;++add) {
if (gcd(add, n) != 1) continue;
boolean ok=false;
DSU ndsu=dsu.copy();
for (int i=1;i<=n;++i) {
for (int j=1;j<=n;++j) {
if (!dsu.equiv(i, j) && i*add%n==j) {
ndsu.union(i, j);
ok=true;
}
}
}
if (ok) vis[grundy(n, ndsu)] = true;
}
int g=0;
while (vis[g])++g;
set.put(dsu.parent, g);
return g;
}
int gcd(int a, int b) {
if (a==0) return b;
return gcd(b%a, a);
}
}
class DSU {
int[] parent;
public DSU(int n) {
parent=new int[n];
Arrays.fill(parent, -1);
}
int root(int x) {
return parent[x] < 0 ? x : (parent[x]=root(parent[x]));
}
void union(int x, int y) {
x=root(x);
y=root(y);
if (x==y) return;
parent[y]+=parent[x];
parent[x]=y;
}
boolean equiv(int x, int y) {
return root(x)==root(y);
}
int size(int x) {
return -parent[root(x)];
}
DSU copy() {
DSU dsu=new DSU(parent.length);
dsu.parent=this.parent.clone();
return dsu;
}
}
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();
}
}