結果
問題 | No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩 |
ユーザー |
|
提出日時 | 2021-06-12 11:13:08 |
言語 | C++17(clang) (17.0.6 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 74 |
ソースコード
#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";}