結果

問題 No.1597 Matrix Sort
コンテスト
ユーザー boatmuscles
提出日時 2021-07-09 23:38:12
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 708 ms / 1,500 ms
コード長 1,212 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,842 ms
コンパイル使用メモリ 111,092 KB
最終ジャッジ日時 2025-01-22 22:47:36
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:26:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |     scanf("%llu %llu %u", &N, &K, &P);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:28:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |     for(int i = 0; i < N; ++i) scanf("%u", &A[i]);
      |                                ~~~~~^~~~~~~~~~~~~
main.cpp:31:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |     for(int i = 0; i < N; ++i) scanf("%u", &B[i]);
      |                                ~~~~~^~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#define _GLIBCXX_DEBUG
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ull N, K;
unsigned P;
ull Solve(int x, vector<unsigned> A, vector<unsigned> B){
    unsigned a, b, c;
    a = (B[0] <= x) ? distance(A.begin(), upper_bound(A.begin(), A.end(), x - B[0])) : 0;
    b = distance(A.begin(), lower_bound(A.begin(), A.end(), P - B[0]));
    c = distance(A.begin(), upper_bound(A.begin(), A.end(), P + x - B[0]));
    ull ret = a + c - b;
    for (unsigned i = 1; i < N; i++){
        while(a > 0 && A[a-1] + B[i] > x ) a--;
        while(b > 0 && A[b-1] + B[i] >= P) b--;
        while(c > 0 && A[c-1] + B[i] > x + P) c--;
        ret += a + c - b;
    }
    return ret;
}

int main(){
    scanf("%llu %llu %u", &N, &K, &P);
    vector<unsigned> A(N);
    for(int i = 0; i < N; ++i) scanf("%u", &A[i]);
    sort(A.begin(), A.end());
    vector<unsigned> B(N);
    for(int i = 0; i < N; ++i) scanf("%u", &B[i]);
    sort(B.begin(), B.end());
    int ok = P-1, ng = -1, mid;
    while(ok - ng > 1){
        mid = ok + ng >>1;
        if(Solve(mid, A, B) >= K) ok = mid;
        else ng = mid;
    }
    printf("%d\n", ok);
	return 0;
}
0