結果
問題 | No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩 |
ユーザー | vkgainz |
提出日時 | 2021-06-12 11:13:08 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 338 ms / 2,000 ms |
コード長 | 3,481 bytes |
コンパイル時間 | 2,704 ms |
コンパイル使用メモリ | 165,072 KB |
実行使用メモリ | 11,248 KB |
最終ジャッジ日時 | 2024-12-16 04:11:26 |
合計ジャッジ時間 | 13,326 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 1 ms
6,816 KB |
testcase_06 | AC | 1 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 3 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 2 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 3 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,820 KB |
testcase_15 | AC | 3 ms
6,816 KB |
testcase_16 | AC | 3 ms
6,816 KB |
testcase_17 | AC | 2 ms
6,816 KB |
testcase_18 | AC | 16 ms
6,820 KB |
testcase_19 | AC | 8 ms
6,816 KB |
testcase_20 | AC | 17 ms
6,820 KB |
testcase_21 | AC | 7 ms
6,820 KB |
testcase_22 | AC | 11 ms
6,820 KB |
testcase_23 | AC | 17 ms
6,816 KB |
testcase_24 | AC | 15 ms
6,816 KB |
testcase_25 | AC | 16 ms
6,820 KB |
testcase_26 | AC | 18 ms
6,820 KB |
testcase_27 | AC | 10 ms
6,820 KB |
testcase_28 | AC | 122 ms
6,816 KB |
testcase_29 | AC | 104 ms
6,816 KB |
testcase_30 | AC | 92 ms
6,820 KB |
testcase_31 | AC | 111 ms
6,816 KB |
testcase_32 | AC | 143 ms
8,260 KB |
testcase_33 | AC | 87 ms
6,816 KB |
testcase_34 | AC | 138 ms
6,888 KB |
testcase_35 | AC | 156 ms
6,924 KB |
testcase_36 | AC | 254 ms
9,456 KB |
testcase_37 | AC | 55 ms
6,820 KB |
testcase_38 | AC | 126 ms
6,820 KB |
testcase_39 | AC | 78 ms
6,820 KB |
testcase_40 | AC | 94 ms
6,816 KB |
testcase_41 | AC | 142 ms
6,816 KB |
testcase_42 | AC | 222 ms
8,004 KB |
testcase_43 | AC | 139 ms
6,816 KB |
testcase_44 | AC | 162 ms
6,820 KB |
testcase_45 | AC | 130 ms
6,820 KB |
testcase_46 | AC | 133 ms
7,488 KB |
testcase_47 | AC | 89 ms
6,816 KB |
testcase_48 | AC | 232 ms
10,480 KB |
testcase_49 | AC | 181 ms
10,480 KB |
testcase_50 | AC | 245 ms
10,480 KB |
testcase_51 | AC | 222 ms
10,480 KB |
testcase_52 | AC | 194 ms
10,480 KB |
testcase_53 | AC | 315 ms
11,116 KB |
testcase_54 | AC | 316 ms
11,120 KB |
testcase_55 | AC | 338 ms
11,248 KB |
testcase_56 | AC | 316 ms
11,244 KB |
testcase_57 | AC | 209 ms
11,116 KB |
testcase_58 | AC | 118 ms
11,248 KB |
testcase_59 | AC | 122 ms
11,120 KB |
testcase_60 | AC | 118 ms
11,068 KB |
testcase_61 | AC | 119 ms
11,248 KB |
testcase_62 | AC | 119 ms
11,116 KB |
testcase_63 | AC | 19 ms
7,664 KB |
testcase_64 | AC | 18 ms
7,660 KB |
testcase_65 | AC | 18 ms
7,792 KB |
testcase_66 | AC | 19 ms
7,664 KB |
testcase_67 | AC | 20 ms
7,664 KB |
testcase_68 | AC | 2 ms
6,820 KB |
testcase_69 | AC | 2 ms
6,820 KB |
testcase_70 | AC | 1 ms
6,816 KB |
testcase_71 | AC | 2 ms
6,816 KB |
testcase_72 | AC | 2 ms
6,816 KB |
testcase_73 | AC | 2 ms
6,820 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; void read(vector<int> &v, int sz) { for(int i = 0; i < sz; i++) { cin >> v[i]; } } long long get_floor(long long lo, long long hi) { long long x = (lo + hi); if(abs(x) % 2 == 0) return x / 2; if(x > 0) return x / 2; return (x - 1) / 2; } long long solve(vector<int> &x, vector<int> &y, long long mid) { int j = (int) y.size() - 1; long long ans = 0LL; for(int i = 0; i < (int) x.size(); i++) { while(j >= 0 && x[i] * 1LL * y[j] > mid) --j; ans += j + 1; } return ans; } long long solve2(vector<int> &x, vector<int> &y, long long mid) { int j = (int) y.size() - 1; long long ans = 0LL; for(int i = 0; i < (int) x.size(); i++) { while(j >= 0 && x[i] * 1LL * y[j] <= mid) --j; ans += (int) y.size() - 1 - j; } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int K, L, M, N; long long S; cin >> K >> L >> M >> N >> S; vector<int> A(K), B(L), C(M), D(N); read(A, K); read(B, L); read(C, M); read(D, N); vector<int> fl, fr; for(int i = 0; i < K; i++) for(int j = 0; j < L; j++) fl.push_back(A[i] * B[j]); sort(fl.begin(), fl.end()); for(int i = 0; i < M; i++) for(int j = 0; j < N; j++) fr.push_back(C[i] * D[j]); sort(fr.begin(), fr.end()); vector<vector<int>> l(2), r(2); int zl = 0, zr = 0; for(int i = 0; i < K; i++) { for(int j = 0; j < L; j++) { if(A[i] * B[j] > 0) l[0].push_back(A[i] * B[j]); else if(A[i] * B[j] == 0) ++zl; else l[1].push_back(A[i] * B[j]); } } for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { if(C[i] * D[j] > 0) r[0].push_back(C[i] * D[j]); else if(C[i] * D[j] == 0) ++zr; else r[1].push_back(C[i] * D[j]); } } for(int i = 0; i < 2; i++) sort(l[i].begin(), l[i].end()), sort(r[i].begin(), r[i].end()); reverse(l[1].begin(), l[1].end()); reverse(r[1].begin(), r[1].end()); long long lo = -1e18, hi = 1e18; for(int j = 0; j < 62; j++) { long long mid = get_floor(lo, hi); long long num = 0LL; num += solve(l[0], r[0], mid); num += solve(l[1], r[1], mid); num += solve2(l[0], r[1], mid); num += solve2(r[0], l[1], mid); if(mid >= 0) num += zl * 1LL * zr + zl * 1LL * M * N + zr * 1LL * K * L; if(num < S) lo = mid + 1; else hi = mid; } long long T = lo; long long left = 0LL, right = 0LL; for(int i = 0; i < K * L; i++) { if(fl[i] == 0) { if(T == 0) left = 0, right = fr[0]; continue; } if(T % fl[i] == 0) { int it = lower_bound(fr.begin(), fr.end(), T / fl[i]) - fr.begin(); if(fr[it] == T / fl[i]) left = fl[i], right = T / fl[i]; } } pair<int, int> x, y; for(int i = 0; i < K; i++) { for(int j = 0; j < L; j++) { if(A[i] * 1LL * B[j] == left) x = {A[i], B[j]}; } } for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { if(C[i] * 1LL * D[j] == right) y = {C[i], D[j]}; } } cout << T << "\n"; cout << x.first << " " << x.second << " " << y.first << " " << y.second << "\n"; }