結果
問題 | No.1730 GCD on Blackboard in yukicoder |
ユーザー |
|
提出日時 | 2021-11-05 22:17:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 943 bytes |
コンパイル時間 | 2,803 ms |
コンパイル使用メモリ | 203,024 KB |
最終ジャッジ日時 | 2025-01-25 12:25:57 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 WA * 8 TLE * 7 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>vector<T> make_divisor(T n) {vector<T> lower, upper;T i = 1;while (i * i <= n) {if (n % i == 0) {lower.push_back(i);if (T j = n / i; i != j) upper.push_back(j);}++i;}std::reverse(std::begin(upper), std::end(upper));std::copy(std::begin(upper), std::end(upper), std::back_inserter(lower));return lower;}int main() {int n;cin >> n;vector<int> a(n);for (auto&& ai : a) cin >> ai;map<int, int> cnt;for (auto&& ai : a) {for (auto&& div : make_divisor(ai)) {cnt[div]++;}}vector<int> ans(n + 1, -1);for (auto& [k, v] : cnt) {ans[n - v] = k;}for (int i = 0; i < n - 1; ++i) {if (ans[i + 1] == -1) ans[i + 1] = ans[i];}for (int i = 0; i < n; ++i) cout << ans[i] << endl;}