結果
問題 | No.1597 Matrix Sort |
ユーザー |
|
提出日時 | 2021-07-24 09:02:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 331 ms / 1,500 ms |
コード長 | 1,455 bytes |
コンパイル時間 | 2,102 ms |
コンパイル使用メモリ | 201,692 KB |
最終ジャッジ日時 | 2025-01-23 09:30:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; #define rep(i,n) for(int i=0;i<(n);i++) #define rrep(i,n) for(int i=(n)-1;i>=0;i--) #define rep1(i,n) for(int i=1;i<=(n);i++) #define rrep1(i,n) for(int i=(n);i>0;i--) #define fore(i_in,a) for (auto& i_in: a) #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define cnts(x,c) count(all(x),c) #define fio() cin.tie(nullptr);ios::sync_with_stdio(false); #define DEBUG_CTN(v) cerr<<#v<<":";for(auto itr=v.begin();itr!=v.end();itr++) cerr<<" "<<*itr; cerr<<endl template<class T> bool chmax(T &a, const T &b) {if (a<b) {a = b; return 1;} return 0;} template<class T> bool chmin(T &a, const T &b) {if (a>b) {a = b; return 1;} return 0;} template<class T> void print(const T &t) {cout<<t<<"\n";} template<class T> void PRINT(const T &t) {rep(i,sz(t)) cout<<t[i]<<" \n"[i==sz(t)-1];} const ll INF = 1LL << 62; const int iINF = 1 << 30; int n; ll k,p; vl a,b; ll check(ll x){ ll cnt=0; fore(y,a){ cnt+=lower_bound(all(b),x-y)-b.begin(); cnt+=lower_bound(all(b),x+p-y)-lower_bound(all(b),p-y); } return cnt; } int main() { fio(); cin>>n>>k>>p; a=b=vl(n); fore(x,a) cin>>x; fore(x,b) cin>>x; sort(all(a));sort(all(b)); ll ng=0,ok=10010010; while(ok-ng>1LL){ ll mid=(ok+ng)/2; if(check(mid)>=k) ok=mid; else ng=mid; } print(ng); }