結果

問題 No.1881 Everything is the same...
ユーザー 👑 hos.lyric
提出日時 2022-03-18 23:03:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,696 bytes
コンパイル時間 1,192 ms
コンパイル使用メモリ 125,440 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-10-03 08:05:35
合計ジャッジ時間 4,699 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int root(vector<int> &uf, int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf, uf[u]));
}
bool connect(vector<int> &uf, int u, int v) {
  u = root(uf, u);
  v = root(uf, v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


int M;
vector<bool> oks;
map<vector<bool>, int> cache;

int calc(vector<bool> fs) {
  vector<int> uf(M, -1);
  for (int a = 1; a < M; ++a) if (fs[a]) {
    for (int u = 0; u < M; ++u) {
      connect(uf, u, (Int)u * a % M);
    }
  }
  for (int a = 1; a < M; ++a) if (root(uf, 1) == root(uf, a)) {
    fs[a] = true;
  }
  
  auto it = cache.find(fs);
  if (it != cache.end()) {
    return it->second;
  }
  
  set<int> app;
  set<int> used;
  for (int a = 1; a < M; ++a) if (oks[a] && !fs[a]) {
    if (used.insert(root(uf, a)).second) {
      auto gs = fs;
      gs[a] = true;
      const int res = calc(gs);
      app.insert(res);
    }
  }
  
  int ret = -1;
  for (int g = 0; ; ++g) {
    if (!app.count(g)) {
      ret = g;
      break;
    }
  }
  return cache[fs] = ret;
}


int solve(int m) {
  M = m;
  oks.assign(m, false);
  for (int a = 1; a < m; ++a) {
    oks[a] = (__gcd(m, a) == 1);
  }
  cache.clear();
  vector<bool> start(m, false);
  return calc(start);
}

int main() {
  /*
  for (int m = 1; m <= 100; ++m) {
    cerr << m << ": " << solve(m) << " " << cache.size() << endl;
  }
  */
  
  int N;
  for (; ~scanf("%d", &N); ) {
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
    }
    sort(A.begin(), A.end());
    
    int ans = 0;
    for (int i = 0, j; i < N; i = j) {
      for (j = i; j < N && A[i] == A[j]; ++j) {}
      if ((j - i) % 2 != 0) {
        ans ^= solve(A[i]);
      }
    }
    puts(ans ? "Y" : "X");
  }
  return 0;
}
0