結果
問題 |
No.2724 Coprime Game 1
|
ユーザー |
|
提出日時 | 2024-12-20 17:09:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,772 ms / 2,000 ms |
コード長 | 880 bytes |
コンパイル時間 | 10,424 ms |
コンパイル使用メモリ | 336,732 KB |
実行使用メモリ | 176,804 KB |
最終ジャッジ日時 | 2024-12-20 17:10:13 |
合計ジャッジ時間 | 22,984 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> constexpr int N = 3e6; std::vector<int> g[N + 1]; int main() { std::cin.tie(nullptr)->sync_with_stdio(false); for (int i = 2; i <= N; ++i) { if (!g[i].empty()) continue; for (int j = i + i; j <= N; j += i) g[j].push_back(i); } int q; std::cin >> q; std::vector<int> queries(q), ord(q), res(q); for (auto &x : queries) std::cin >> x; std::iota(ord.begin(), ord.end(), 0); std::ranges::sort(ord, {}, [&](int i) {return queries[i];}); int u = 2; atcoder::dsu d(N + 1); for (auto &i : ord) { int n = queries[i]; while (u <= n) { for (auto &v : g[u]) d.merge(u, v); u += 1; } res[i] = d.size(n) & 1; } for (auto &x : res) std::cout << (x ? "P" : "K") << '\n'; return 0; }