結果
問題 | No.1597 Matrix Sort |
ユーザー |
![]() |
提出日時 | 2021-07-09 22:05:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 1,500 ms |
コード長 | 623 bytes |
コンパイル時間 | 2,170 ms |
コンパイル使用メモリ | 198,056 KB |
最終ジャッジ日時 | 2025-01-22 21:50:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int n,p; ll k; cin>>n>>k>>p; vector<int> a(n),b(n); for(int &x:a){ cin>>x; x%=p; } for(int &x:b){ cin>>x; x%=p; } sort(a.begin(),a.end()); sort(b.begin(),b.end()); int lo=0,hi=p; while(hi-lo>1){ int mid=(lo+hi)/2; ll cnt=0; int j1=n-1,j2=n-1,j3=n-1; for(int i=0;i<n;i++){ while(j1>=0&&a[i]+b[j1]>=mid)j1--; while(j2>=0&&a[i]+b[j2]>=p)j2--; while(j3>=0&&a[i]+b[j3]>=p+mid)j3--; cnt+=j1+1+j3-j2; } if(cnt>=k)hi=mid; else lo=mid; } cout<<lo<<endl; }