結果
問題 | No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩 |
ユーザー |
![]() |
提出日時 | 2020-11-01 18:03:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 635 ms / 2,000 ms |
コード長 | 2,949 bytes |
コンパイル時間 | 1,294 ms |
コンパイル使用メモリ | 91,988 KB |
最終ジャッジ日時 | 2025-01-15 18:47:17 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 74 |
ソースコード
#include<algorithm>#include<cassert>#include<iostream>#include<vector>using namespace std;typedef long long lint;typedef vector<int>vi;typedef pair<lint,int>pli;#define rep(i,n)for(int i=0;i<(int)(n);++i)int k,l,m,n;lint s;const int N=601;const int NLIMIT=600;const lint VLIMIT=30000;lint a[N],b[N],c[N],d[N];void in_range(lint a,lint b,lint c){assert(b<=a&&a<=c);}lint quo(lint a,lint b){assert(b>0);lint q=a/b;if(a<q*b)q--;return q;}int main(){cin>>k>>l>>m>>n>>s;rep(i,k)cin>>a[i];rep(i,l)cin>>b[i];rep(i,m)cin>>c[i];rep(i,n)cin>>d[i];//入力が妥当か確認する。in_range(k,1,NLIMIT);in_range(l,1,NLIMIT);in_range(m,1,NLIMIT);in_range(n,1,NLIMIT);in_range(s,1,lint(k)*l*m*n);rep(i,k)in_range(a[i],-VLIMIT,VLIMIT);rep(i,l)in_range(b[l],-VLIMIT,VLIMIT);rep(i,m)in_range(c[m],-VLIMIT,VLIMIT);rep(i,n)in_range(d[n],-VLIMIT,VLIMIT);//平方分割vector<pli>frm;vector<lint>lat,latneg,latpos;lint lat0=0;rep(i,k)rep(j,l)frm.push_back(pli(a[i]*b[j],i*l+j));rep(i,m)rep(j,n)lat.push_back(c[i]*d[j]);sort(frm.begin(),frm.end());for(lint x:lat){if(x>0)latpos.push_back(x);if(x<0)latneg.push_back(-x);if(x==0)lat0++;}sort(latpos.begin(),latpos.end());sort(latneg.rbegin(),latneg.rend());//二分探索。x 以下の要素が s 個以上になる最小の x が欲しい。//8.1*10^17 を包む値lint pass=1e18,fail=-1e18;while(pass-fail>1){lint mid=fail+(pass-fail)/2;lint count=mid>=0?lat0*k*l:0;int pos=k*l;//尺取りif(mid>=0){rep(i,latpos.size()){lint div=latpos[i];lint q=quo(mid,div);while(pos>0&&frm[pos-1].first>q)pos--;count+=pos;}pos=0;for(int i=(int)latneg.size()-1;i>=0;i--){lint div=latneg[i];lint q=quo(-mid+div-1,div);while(pos<k*l&&frm[pos].first<q)pos++;count+=k*l-pos;}}else{for(int i=(int)latpos.size()-1;i>=0;i--){lint div=latpos[i];lint q=quo(mid,div);while(pos>0&&frm[pos-1].first>q)pos--;count+=pos;}pos=0;rep(i,latneg.size()){lint div=latneg[i];lint q=quo(-mid+div-1,div);while(pos<k*l&&frm[pos].first<q)pos++;count+=k*l-pos;}}if(count>=s)pass=mid;else fail=mid;}cout<<pass<<endl;rep(i,m*n){// 解が見つかる?int i0=i/n,i1=i%n;lint div=lat[i];if(div==0){if(pass==0){cout<<a[0]<<" "<<b[0]<<" "<<c[i0]<<" "<<d[i1]<<endl;return 0;}else continue;}if(pass%div!=0)continue;lint q=pass/div;int idx=lower_bound(frm.begin(),frm.end(),pli(q,-1))-frm.begin();if(frm[idx].first==q){int j0=frm[idx].second/l;int j1=frm[idx].second%l;cout<<a[j0]<<" "<<b[j1]<<" "<<c[i0]<<" "<<d[i1]<<endl;return 0;}}assert(0);}