結果
問題 | No.854 公平なりんご分配 |
ユーザー | kotamanegi |
提出日時 | 2019-07-26 21:52:43 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 439 ms / 3,153 ms |
コード長 | 3,525 bytes |
コンパイル時間 | 1,333 ms |
コンパイル使用メモリ | 116,168 KB |
実行使用メモリ | 124,644 KB |
最終ジャッジ日時 | 2023-08-20 12:39:06 |
合計ジャッジ時間 | 11,292 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,384 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,384 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 2 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,380 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 4 ms
4,384 KB |
testcase_23 | AC | 4 ms
5,720 KB |
testcase_24 | AC | 6 ms
5,748 KB |
testcase_25 | AC | 3 ms
4,380 KB |
testcase_26 | AC | 6 ms
4,648 KB |
testcase_27 | AC | 5 ms
4,688 KB |
testcase_28 | AC | 4 ms
4,384 KB |
testcase_29 | AC | 3 ms
4,376 KB |
testcase_30 | AC | 3 ms
4,380 KB |
testcase_31 | AC | 6 ms
4,460 KB |
testcase_32 | AC | 41 ms
30,444 KB |
testcase_33 | AC | 46 ms
18,616 KB |
testcase_34 | AC | 82 ms
40,216 KB |
testcase_35 | AC | 59 ms
32,612 KB |
testcase_36 | AC | 42 ms
6,360 KB |
testcase_37 | AC | 39 ms
27,916 KB |
testcase_38 | AC | 31 ms
23,308 KB |
testcase_39 | AC | 133 ms
41,224 KB |
testcase_40 | AC | 53 ms
15,456 KB |
testcase_41 | AC | 56 ms
27,472 KB |
testcase_42 | AC | 72 ms
39,324 KB |
testcase_43 | AC | 90 ms
27,224 KB |
testcase_44 | AC | 92 ms
36,960 KB |
testcase_45 | AC | 93 ms
10,432 KB |
testcase_46 | AC | 121 ms
36,224 KB |
testcase_47 | AC | 45 ms
22,096 KB |
testcase_48 | AC | 64 ms
38,508 KB |
testcase_49 | AC | 65 ms
39,772 KB |
testcase_50 | AC | 37 ms
27,796 KB |
testcase_51 | AC | 127 ms
38,320 KB |
testcase_52 | AC | 87 ms
18,520 KB |
testcase_53 | AC | 44 ms
17,988 KB |
testcase_54 | AC | 88 ms
20,944 KB |
testcase_55 | AC | 32 ms
18,312 KB |
testcase_56 | AC | 26 ms
18,520 KB |
testcase_57 | AC | 43 ms
16,068 KB |
testcase_58 | AC | 82 ms
9,892 KB |
testcase_59 | AC | 23 ms
14,368 KB |
testcase_60 | AC | 58 ms
16,016 KB |
testcase_61 | AC | 30 ms
5,852 KB |
testcase_62 | AC | 69 ms
14,608 KB |
testcase_63 | AC | 55 ms
15,444 KB |
testcase_64 | AC | 21 ms
9,112 KB |
testcase_65 | AC | 52 ms
34,308 KB |
testcase_66 | AC | 43 ms
11,168 KB |
testcase_67 | AC | 71 ms
23,336 KB |
testcase_68 | AC | 74 ms
12,196 KB |
testcase_69 | AC | 50 ms
41,668 KB |
testcase_70 | AC | 27 ms
16,572 KB |
testcase_71 | AC | 32 ms
16,716 KB |
testcase_72 | AC | 59 ms
5,700 KB |
testcase_73 | AC | 44 ms
28,620 KB |
testcase_74 | AC | 85 ms
33,492 KB |
testcase_75 | AC | 46 ms
17,048 KB |
testcase_76 | AC | 70 ms
28,136 KB |
testcase_77 | AC | 75 ms
37,524 KB |
testcase_78 | AC | 89 ms
14,276 KB |
testcase_79 | AC | 84 ms
24,872 KB |
testcase_80 | AC | 79 ms
26,312 KB |
testcase_81 | AC | 58 ms
26,216 KB |
testcase_82 | AC | 296 ms
124,556 KB |
testcase_83 | AC | 411 ms
124,520 KB |
testcase_84 | AC | 439 ms
124,556 KB |
testcase_85 | AC | 427 ms
124,556 KB |
testcase_86 | AC | 172 ms
124,540 KB |
testcase_87 | AC | 292 ms
124,544 KB |
testcase_88 | AC | 300 ms
124,548 KB |
testcase_89 | AC | 299 ms
124,528 KB |
testcase_90 | AC | 300 ms
124,576 KB |
testcase_91 | AC | 288 ms
124,540 KB |
testcase_92 | AC | 432 ms
124,552 KB |
testcase_93 | AC | 432 ms
124,644 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <cstring> #include <queue> #include <stack> #include <math.h> #include <iterator> #include <vector> #include <string> #include <set> #include <math.h> #include <iostream> #include <random> #include<map> #include <iomanip> #include <time.h> #include <stdlib.h> #include <list> #include <typeinfo> #include <list> #include <set> #include <cassert> #include<fstream> #include <unordered_map> #include <cstdlib> #include <complex> #include <cctype> #include <bitset> using namespace std; typedef string::const_iterator State; #define Ma_PI 3.141592653589793 #define eps 0.00000001 #define LONG_INF 1e18 #define GOLD 1.61803398874989484820458 #define MAX_MOD 1000000007 #define MOD 998244353 #define seg_size 262144 #define REP(a,b) for(long long a = 0;a < b;++a) vector<complex<double>> DFT(vector<complex<double>> a) { int n = a.size(); if (n == 1) return a; vector<complex<double>> a0(n / 2), a1(n / 2); REP(i, n) { if (i % 2 == 0) { a0[i / 2] = a[i]; } else { a1[i / 2] = a[i]; } } vector<complex<double>> inversed_a0 = DFT(a0), inversed_a1 = DFT(a1); vector<complex<double>> inversed_a(n); for (int i = 0; i < n; ++i) { complex<double> zeta = complex<double>(cos(2 * Ma_PI * i / n), sin(2 * Ma_PI * i / n)); inversed_a[i] = inversed_a0[i % (n / 2)] + zeta * inversed_a1[i % (n / 2)]; } return inversed_a; } vector<complex<double>> IDFT(vector<complex<double>> inversed_a) { int n = inversed_a.size(); vector<complex<double>> now = DFT(inversed_a); reverse(now.begin(), now.end()); for (int q = now.size() - 1; q >= 1; --q) { swap(now[q], now[q - 1]); } REP(i, n) { now[i] /= complex<double>(n, 0); } return now; } vector<complex<double>> conv(vector<complex<double>> a, vector<complex<double>> b) { int deg = a.size() + b.size() - 1; int n = 1; while (n < deg) n <<= 1; a.resize(n); b.resize(n); vector<complex<double>> inversed_a = DFT(a), inversed_b = DFT(b); vector<complex<double>> inversed_c(n); REP(i, n) { inversed_c[i] = inversed_a[i] * inversed_b[i]; } return IDFT(inversed_c); } long long inv(long long now) { long long hoge = MOD - 2LL; long long ans = 1; while (hoge != 0) { if (hoge % 2 == 1) { ans *= now; ans %= MOD; } hoge /= 2; now *= now; now %= MOD; } return ans; } int sums[100002][310] = {}; int main() { iostream::sync_with_stdio(false); vector<long long> sosuu; for (long long q = 2; q <= 2000; ++q) { int ok = 1; for (long long j = 2; j <= sqrt(q); ++j) { if (q % j == 0) ok = 0; } if (ok == 1) { sosuu.push_back(q); } } long long n; cin >> n; for(int i = 1;i <= n;++i){ long long a; cin >> a; REP(j, sosuu.size()+1) { sums[i][j] = sums[i - 1][j]; } if (a == 0) { sums[i][sosuu.size()]++; continue; } for (int q = 0;q < sosuu.size(); ++q) { while (a % sosuu[q] == 0) { sums[i][q]++; a /= sosuu[q]; } } } int query; cin >> query; REP(i, query) { long long a, b, c; cin >> a >> b >> c; b--; if (sums[c][sosuu.size()] - sums[b][sosuu.size()] >= 1) { cout << "Yes" << endl; continue; } long long ok = 1; for (int q = 0; q < sosuu.size(); ++q) { int cnt = 0; while (a % sosuu[q] == 0) { cnt++; a /= sosuu[q]; } if (sums[c][q] - sums[b][q] < cnt) { ok = 0; break; } } if (a >= 2000) { ok = 0; } if (ok == 1) { cout << "Yes" << endl; } else { cout << "NO" << endl; } } }