結果
問題 | No.2929 Miracle Branch |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:40:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 332 ms / 2,000 ms |
コード長 | 1,377 bytes |
コンパイル時間 | 1,097 ms |
コンパイル使用メモリ | 82,868 KB |
最終ジャッジ日時 | 2025-02-24 18:39:31 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <algorithm> #include <iostream> #include <numeric> #include <vector> using Int = long long; int main() { int N = 200000; Int X; std::cin >> X; std::vector<Int> A; for (Int i = 2; i * i <= X && i <= N; ++i) while (X % i == 0) { X /= i; A.push_back(i); } if (X > 1) A.push_back(X); reverse(A.begin(), A.end()); int M = A.size(); for (int i = 0; i < M; ++i) { if (A[i] > N) { std::cout << -1 << std::endl; return 0; } } int n = N + 1; std::vector<int> u, v; std::vector<char> c; for (int i = 1; i <= 100; ++i) { std::vector<Int> B(i, 1); for (int j = 0; j < M; ++j) { int id = min_element(B.begin(), B.end()) - B.begin(); B[id] *= A[j]; } Int x = std::accumulate(B.begin(), B.end(), 0LL) + i; if (x < n) { n = x; u.clear(); v.clear(); c.clear(); int j = i + 1; for (int k = 0; k < i - 1; ++k) { u.push_back(k + 1); v.push_back(k + 2); } for (int k = 0; k < i; ++k) { for (int l = 0; l < B[k]; ++l) { u.push_back(k + 1); v.push_back(j++); } c.push_back('b'); } while (int(c.size()) < n) { c.push_back('g'); } } } if (n <= N) { std::cout << n << std::endl; for (int i = 0; i < n - 1; ++i) std::cout << u[i] << ' ' << v[i] << std::endl; for (int i = 0; i < n; ++i) std::cout << c[i] << " \n"[i == n - 1]; } else { std::cout << -1 << std::endl; } }