結果
問題 | No.2718 Best Consonance |
ユーザー | 👑 emthrm |
提出日時 | 2024-04-05 22:28:51 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,194 bytes |
コンパイル時間 | 3,497 ms |
コンパイル使用メモリ | 277,212 KB |
実行使用メモリ | 291,784 KB |
最終ジャッジ日時 | 2024-04-07 00:13:25 |
合計ジャッジ時間 | 35,869 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
13,584 KB |
testcase_01 | AC | 9 ms
13,584 KB |
testcase_02 | AC | 9 ms
13,584 KB |
testcase_03 | AC | 9 ms
13,584 KB |
testcase_04 | AC | 9 ms
13,584 KB |
testcase_05 | AC | 9 ms
13,584 KB |
testcase_06 | AC | 10 ms
13,584 KB |
testcase_07 | AC | 9 ms
13,584 KB |
testcase_08 | AC | 9 ms
13,584 KB |
testcase_09 | AC | 12 ms
13,716 KB |
testcase_10 | AC | 12 ms
13,716 KB |
testcase_11 | AC | 12 ms
13,716 KB |
testcase_12 | AC | 13 ms
13,716 KB |
testcase_13 | AC | 12 ms
13,716 KB |
testcase_14 | AC | 1,060 ms
41,196 KB |
testcase_15 | AC | 820 ms
35,464 KB |
testcase_16 | AC | 933 ms
37,096 KB |
testcase_17 | AC | 675 ms
32,476 KB |
testcase_18 | AC | 903 ms
38,468 KB |
testcase_19 | AC | 720 ms
34,524 KB |
testcase_20 | AC | 1,172 ms
41,196 KB |
testcase_21 | AC | 1,054 ms
40,092 KB |
testcase_22 | AC | 1,057 ms
40,244 KB |
testcase_23 | AC | 514 ms
30,708 KB |
testcase_24 | AC | 1,904 ms
43,188 KB |
testcase_25 | AC | 1,357 ms
43,316 KB |
testcase_26 | AC | 1,147 ms
43,188 KB |
testcase_27 | AC | 1,364 ms
43,444 KB |
testcase_28 | AC | 1,424 ms
43,316 KB |
testcase_29 | AC | 1,299 ms
43,316 KB |
testcase_30 | AC | 1,415 ms
43,316 KB |
testcase_31 | AC | 1,936 ms
43,188 KB |
testcase_32 | AC | 1,460 ms
43,316 KB |
testcase_33 | AC | 1,322 ms
43,188 KB |
testcase_34 | AC | 10 ms
13,584 KB |
testcase_35 | AC | 10 ms
13,584 KB |
testcase_36 | AC | 1,854 ms
86,068 KB |
testcase_37 | AC | 10 ms
13,584 KB |
testcase_38 | TLE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template <bool GETS_ONLY_PRIME> std::vector<int> prime_sieve(const int n) { std::vector<int> smallest_prime_factor(n + 1), prime; std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0); for (int i = 2; i <= n; ++i) { if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i); for (const int p : prime) { if (i * p > n || p > smallest_prime_factor[i]) break; smallest_prime_factor[i * p] = p; } } return GETS_ONLY_PRIME ? prime : smallest_prime_factor; } struct Divisor { const std::vector<int> smallest_prime_factor; explicit Divisor(const int n) : smallest_prime_factor(prime_sieve<false>(n)) {} std::vector<int> query(int n) const { std::vector<int> res{1}; while (n > 1) { const int prime_factor = smallest_prime_factor[n], d = res.size(); int tmp = 1; for (; n % prime_factor == 0; n /= prime_factor) { tmp *= prime_factor; for (int i = 0; i < d; ++i) { res.emplace_back(res[i] * tmp); } } } // std::sort(res.begin(), res.end()); return res; } }; int main() { constexpr int A = 200000; const Divisor divisor(A); int n; cin >> n; vector<int> a(n), b(n); REP(i, n) cin >> a[i] >> b[i]; array<vector<int>, A + 1> ar1{}, ar2{}; REP(i, n) for (const int g : divisor.query(a[i])) ar1[g].emplace_back(i); vector<int> gs; REP(g, A + 1) { if (ar1[g].size() >= 2) { ranges::sort(ar1[g], {}, [&b](const int i) -> int { return b[i]; }); ar2[g].reserve(ar1[g].size()); ranges::copy(ar1[g], back_inserter(ar2[g])); ranges::sort(ar2[g], {}, [&a](const int i) -> int { return a[i]; }); gs.emplace_back(g); } } int lb = 0, ub = ranges::max(b) + 1; while (ub - lb > 1) { const int f = midpoint(lb, ub); (ranges::any_of(gs, [&](const int g) -> bool { int j = 0; set<pair<ll, int>> st; for (const int i : ar1[g]) { for (; j < ar2[g].size() && ll{a[ar2[g][j]]} * f <= ll{b[i]} * g; ++j) { st.emplace(ll{b[ar2[g][j]]} * g, ar2[g][j]); if (st.size() >= 3) st.erase(st.begin()); } for (const auto& [gb, id] : st) { if (id != i && gb >= ll{a[i]} * f) return true; } } return false; }) ? lb : ub) = f; } cout << lb << '\n'; return 0; }