結果
問題 | No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩 |
ユーザー |
![]() |
提出日時 | 2021-01-22 22:25:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,599 ms / 2,000 ms |
コード長 | 5,502 bytes |
コンパイル時間 | 2,122 ms |
コンパイル使用メモリ | 136,484 KB |
最終ジャッジ日時 | 2025-01-18 04:39:30 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 74 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <stack>#include <array>#include <list>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;int main(){int k, l, m, n; cin>>k>>l>>m>>n;ll s; cin>>s;ll a[606], b[606], c[606], d[606];for(int i=0; i<k; i++) cin>>a[i];for(int i=0; i<l; i++) cin>>b[i];for(int i=0; i<m; i++) cin>>c[i];for(int i=0; i<n; i++) cin>>d[i];vector<ll> ab, cd;for(int i=0; i<k; i++) for(int j=0; j<l; j++) ab.push_back(a[i]*b[j]);for(int i=0; i<m; i++) for(int j=0; j<n; j++) cd.push_back(c[i]*d[j]);sort(ab.begin(), ab.end());sort(cd.begin(), cd.end());ll i1=lower_bound(ab.begin(), ab.end(), 0)-ab.begin();ll i2=upper_bound(ab.begin(), ab.end(), 0)-ab.begin();ll j1=lower_bound(cd.begin(), cd.end(), 0)-cd.begin();ll j2=upper_bound(cd.begin(), cd.end(), 0)-cd.begin();ll kl=ab.size(), mn=cd.size();ll c1=i1*(mn-j2)+j1*(kl-i2);if(s<=c1){vector<ll> v1, v2, w1, w2;for(int i=0; i<kl; i++){if(ab[i]<0) v1.push_back(-ab[i]);else if(ab[i]>0) v2.push_back(ab[i]);}for(int i=0; i<mn; i++){if(cd[i]<0) w1.push_back(-cd[i]);else if(cd[i]>0) w2.push_back(cd[i]);}reverse(v1.begin(), v1.end());reverse(w1.begin(), w1.end());s=c1+1-s;ll le=0, r=1e18;while(r-le>1){ll mid=(le+r)/2;ll cnt=0;for(auto z:v1){cnt+=upper_bound(w2.begin(), w2.end(), mid/z)-w2.begin();}for(auto z:v2){cnt+=upper_bound(w1.begin(), w1.end(), mid/z)-w1.begin();}if(cnt>=s) r=mid;else le=mid;}cout<<-r<<endl;int p1=0, p2=0;for(int i=0; i<kl; i++){if(ab[i]!=0 && r%ab[i]==0){int t=lower_bound(cd.begin(), cd.end(), -r/ab[i])-cd.begin();if(t<mn && cd[t]==-r/ab[i]){p1=i, p2=t;break;}}}bool ok=0;for(int i=0; i<k; i++){for(int j=0; j<l; j++){if(a[i]*b[j]==ab[p1]){cout<<a[i]<<" "<<b[j]<<" ";ok=1;break;}}if(ok)break;}for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(c[i]*d[j]==cd[p2]){cout<<c[i]<<" "<<d[j]<<endl;return 0;}}}}else if(s<=kl*mn-i1*j1-(kl-i2)*(mn-j2)){cout<<0<<endl;for(int i=0; i<k; i++){if(a[i]==0){cout<<0<<" "<<b[0]<<" "<<c[0]<<" "<<d[0]<<endl;return 0;}}for(int i=0; i<l; i++){if(b[i]==0){cout<<a[0]<<" "<<0<<" "<<c[0]<<" "<<d[0]<<endl;return 0;}}for(int i=0; i<m; i++){if(c[i]==0){cout<<a[0]<<" "<<b[0]<<" "<<0<<" "<<d[0]<<endl;return 0;}}for(int i=0; i<n; i++){if(d[i]==0){cout<<a[0]<<" "<<b[0]<<" "<<c[0]<<" "<<0<<endl;return 0;}}}else{s-=kl*mn-i1*j1-(kl-i2)*(mn-j2);vector<ll> v1, v2, w1, w2;for(int i=0; i<kl; i++){if(ab[i]<0) v1.push_back(-ab[i]);else if(ab[i]>0) v2.push_back(ab[i]);}for(int i=0; i<mn; i++){if(cd[i]<0) w1.push_back(-cd[i]);else if(cd[i]>0) w2.push_back(cd[i]);}reverse(v1.begin(), v1.end());reverse(w1.begin(), w1.end());ll le=0, r=1e18;while(r-le>1){ll mid=(le+r)/2;ll cnt=0;for(auto z:v1){cnt+=upper_bound(w1.begin(), w1.end(), mid/z)-w1.begin();}for(auto z:v2){cnt+=upper_bound(w2.begin(), w2.end(), mid/z)-w2.begin();}if(cnt>=s) r=mid;else le=mid;}cout<<r<<endl;int p1=0, p2=0;for(int i=0; i<kl; i++){if(ab[i]!=0 && r%ab[i]==0){int t=lower_bound(cd.begin(), cd.end(), r/ab[i])-cd.begin();if(t<mn && cd[t]*ab[i]==r){p1=i, p2=t;break;}}}bool ok=0;for(int i=0; i<k; i++){for(int j=0; j<l; j++){if(a[i]*b[j]==ab[p1]){cout<<a[i]<<" "<<b[j]<<" ";ok=1;break;}}if(ok)break;}for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(c[i]*d[j]==cd[p2]){cout<<c[i]<<" "<<d[j]<<endl;return 0;}}}}return 0;}