結果
問題 | No.854 公平なりんご分配 |
ユーザー |
![]() |
提出日時 | 2019-07-26 23:03:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,823 bytes |
コンパイル時間 | 678 ms |
コンパイル使用メモリ | 75,108 KB |
実行使用メモリ | 252,032 KB |
最終ジャッジ日時 | 2024-07-02 09:05:41 |
合計ジャッジ時間 | 21,900 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 57 WA * 35 |
ソースコード
#include <iostream> #include <vector> #define int long long using namespace std; int PRIME_SIZE; int MAX_APPLE = 2019; signed main() { vector<int> prime; for (int i = 2; i <= MAX_APPLE; i++) { bool flag = true; for (auto x:prime) { if (x * x > i)break; if (i % x == 0)flag = false; } if (flag)prime.push_back(i); } PRIME_SIZE = prime.size(); vector<vector<int>> factoring(MAX_APPLE + 1, vector<int>(PRIME_SIZE)); for (int i = 1; i <= MAX_APPLE; i++) { int x = i; for (int j = 0; j < PRIME_SIZE; j++) { while (x % prime[j] == 0) { x /= prime[j]; factoring[i][j]++; } } } int n; cin >> n; vector<vector<int>> cumulative_sum(n + 1, vector<int>(PRIME_SIZE)); int zero_count[n + 1]; for (int i = 1; i <= n; i++) { int now; cin >> now; for (int j = 0; j < PRIME_SIZE; j++) cumulative_sum[i][j] = cumulative_sum[i - 1][j] + factoring[now][j]; zero_count[i] = zero_count[i - 1] + (now == 0); } int q; cin >> q; for (int i = 0; i < q; i++) { int p, l, r; cin >> p >> l >> r; vector<int> needed(PRIME_SIZE); for (int j = 0; j < PRIME_SIZE; j++) { while (p % prime[j] == 0) { p /= prime[j]; needed[j]++; } } if (p != 1) { cout << (zero_count[r] - zero_count[l - 1] ? "Yes" : "NO") << endl; continue; } bool ret = true; for (int j = 0; j < PRIME_SIZE; j++) { if (cumulative_sum[r][j] - cumulative_sum[l - 1][j] < needed[j]) ret = false; } cout << (ret ? "Yes" : "NO") << endl; } return 0; }