結果
問題 | No.1730 GCD on Blackboard in yukicoder |
ユーザー |
![]() |
提出日時 | 2021-11-12 10:05:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,028 bytes |
コンパイル時間 | 2,160 ms |
コンパイル使用メモリ | 203,056 KB |
最終ジャッジ日時 | 2025-01-25 15:23:26 |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 4 WA * 3 RE * 9 TLE * 8 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, n) for (int i=0; i<(int)(n); ++(i))#define rep3(i, m, n) for (int i=(m); (i)<(int)(n); ++(i))#define repr(i, n) for (int i=(int)(n)-1; (i)>=0; --(i))#define rep3r(i, m, n) for (int i=(int)(n)-1; (i)>=(int)(m); --(i))#define all(x) (x).begin(), (x).end()//ll gcd(ll a, ll b) { return (b ? gcd(b, a%b) : a); }int main() {int n;cin >> n;vector<ll> a(n);rep(i, n) cin >> a[i];map<ll, int> avals;rep(i, n) avals[a[i]]++;int alen = avals.size();map<ll, int> gvals;for (auto pi : avals) {map<ll, int> adds;adds[pi.first] = pi.second;for (auto itr=gvals.begin(); itr!=gvals.end(); ++itr) adds[gcd(itr->first, pi.first)] += itr->second + pi.second;for (auto api : adds) gvals[api.first] += api.second;}vector<ll> mvals(n+1);for (auto pi : gvals) mvals[pi.second] = max(mvals[pi.second], pi.first);repr(i, n) mvals[i] = max(mvals[i], mvals[i+1]);rep3r(i, 1, n+1) cout << mvals[i] << endl;return 0;}