Submission #10151716


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
template <typename T> istream & operator >> (istream & in, vector<T> & xs) { REP (i, xs.size()) { in >> xs[i]; } return in; }

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;
        (p(m) ? r : l) = m;
    }
    return r;
}

int64_t solve(int64_t n, int64_t k, const vector<int64_t> & a) {
    vector<int64_t> nonnegative, negative;
    for (int64_t a_i : a) {
        (a_i >= 0 ? nonnegative : negative).push_back(a_i);
    }
    sort(ALL(nonnegative));
    sort(ALL(negative));
    reverse(ALL(negative));

    auto count_lt = [&](int64_t x) {
        int64_t cnt = 0;
        for (int64_t a_i : nonnegative) {
            cnt += binsearch(0, nonnegative.size(), [&](int j) {
                return a_i * nonnegative[j] >= x;
            });
            cnt += negative.size() - binsearch(0, negative.size(), [&](int j) {
                return a_i * negative[j] < x;
            });
        }
        for (int64_t a_i : negative) {
            cnt += nonnegative.size() - binsearch(0, nonnegative.size(), [&](int j) {
                return a_i * nonnegative[j] < x;
            });
            cnt += binsearch(0, negative.size(), [&](int j) {
                return a_i * negative[j] >= x;
            });
        }
        for (int64_t a_i : a) {
            cnt -= (a_i * a_i < x);
        }
        return cnt / 2;
    };
    return binsearch(-2e18, 2e18, [&](int64_t x) {
        return count_lt(x + 1) >= k;
    });
}

int main() {
    int64_t n, k; cin >> n >> k;
    vector<int64_t> a(n); cin >> a;
    cout << solve(n, k, a) << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Pairs
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2053 Byte
Status
Exec Time 1959 ms
Memory 4084 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 400 / 400 sample_01.txt, sample_02.txt, sample_03.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_small_01.txt, sub1_small_02.txt, sub1_small_03.txt, sub1_small_04.txt, sub1_small_05.txt, sub1_small_06.txt, sub1_small_07.txt, sub1_small_08.txt, sub1_small_09.txt, sub1_small_10.txt, sub1_small_11.txt, sub1_small_12.txt, sub1_small_13.txt, sub1_small_14.txt, sub1_small_15.txt, sub1_small_16.txt, sub1_small_17.txt, sub1_small_18.txt, sub1_small_19.txt, sub1_small_20.txt, sub1_small_21.txt, sub1_small_22.txt, sub1_small_23.txt, sub1_small_24.txt, sub1_small_25.txt, sub1_small_26.txt, sub1_small_27.txt, sub1_small_28.txt, sub1_small_29.txt, sub1_small_30.txt, sub1_small_31.txt, sub1_small_32.txt, sub1_small_33.txt, sub1_small_34.txt, sub1_small_35.txt, sub1_small_36.txt, sub1_small_37.txt, sub1_small_38.txt, sub1_small_39.txt, sub1_small_40.txt, sub1_small_41.txt, sub1_small_42.txt, sub1_small_43.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sub1_01.txt 710 ms 1912 KB
sub1_02.txt 1336 ms 2888 KB
sub1_03.txt 1915 ms 3524 KB
sub1_04.txt 1042 ms 2684 KB
sub1_05.txt 686 ms 1788 KB
sub1_06.txt 225 ms 768 KB
sub1_07.txt 1534 ms 3140 KB
sub1_08.txt 1695 ms 3440 KB
sub1_09.txt 1306 ms 2888 KB
sub1_10.txt 293 ms 1024 KB
sub1_11.txt 1680 ms 3440 KB
sub1_12.txt 188 ms 768 KB
sub1_13.txt 1395 ms 3312 KB
sub1_14.txt 635 ms 1788 KB
sub1_15.txt 196 ms 768 KB
sub1_16.txt 1628 ms 3440 KB
sub1_17.txt 852 ms 2040 KB
sub1_18.txt 79 ms 512 KB
sub1_19.txt 1894 ms 3696 KB
sub1_20.txt 1027 ms 2296 KB
sub1_21.txt 1840 ms 4084 KB
sub1_22.txt 784 ms 2168 KB
sub1_23.txt 573 ms 2168 KB
sub1_24.txt 385 ms 1912 KB
sub1_25.txt 247 ms 1276 KB
sub1_26.txt 1251 ms 3012 KB
sub1_27.txt 1080 ms 3956 KB
sub1_28.txt 1950 ms 3696 KB
sub1_29.txt 1865 ms 3696 KB
sub1_30.txt 1927 ms 3696 KB
sub1_31.txt 1946 ms 3696 KB
sub1_32.txt 1959 ms 3696 KB
sub1_33.txt 1929 ms 3696 KB
sub1_small_01.txt 6 ms 256 KB
sub1_small_02.txt 2 ms 256 KB
sub1_small_03.txt 9 ms 256 KB
sub1_small_04.txt 5 ms 256 KB
sub1_small_05.txt 3 ms 256 KB
sub1_small_06.txt 10 ms 256 KB
sub1_small_07.txt 3 ms 256 KB
sub1_small_08.txt 6 ms 256 KB
sub1_small_09.txt 4 ms 256 KB
sub1_small_10.txt 5 ms 256 KB
sub1_small_11.txt 6 ms 256 KB
sub1_small_12.txt 9 ms 256 KB
sub1_small_13.txt 3 ms 256 KB
sub1_small_14.txt 10 ms 256 KB
sub1_small_15.txt 2 ms 256 KB
sub1_small_16.txt 10 ms 256 KB
sub1_small_17.txt 3 ms 256 KB
sub1_small_18.txt 2 ms 256 KB
sub1_small_19.txt 1 ms 256 KB
sub1_small_20.txt 9 ms 256 KB
sub1_small_21.txt 8 ms 256 KB
sub1_small_22.txt 9 ms 256 KB
sub1_small_23.txt 1 ms 256 KB
sub1_small_24.txt 1 ms 256 KB
sub1_small_25.txt 3 ms 256 KB
sub1_small_26.txt 3 ms 256 KB
sub1_small_27.txt 6 ms 256 KB
sub1_small_28.txt 4 ms 256 KB
sub1_small_29.txt 8 ms 256 KB
sub1_small_30.txt 3 ms 256 KB
sub1_small_31.txt 10 ms 256 KB
sub1_small_32.txt 6 ms 256 KB
sub1_small_33.txt 8 ms 256 KB
sub1_small_34.txt 6 ms 256 KB
sub1_small_35.txt 8 ms 256 KB
sub1_small_36.txt 2 ms 256 KB
sub1_small_37.txt 7 ms 256 KB
sub1_small_38.txt 4 ms 256 KB
sub1_small_39.txt 3 ms 256 KB
sub1_small_40.txt 11 ms 256 KB
sub1_small_41.txt 2 ms 256 KB
sub1_small_42.txt 2 ms 256 KB
sub1_small_43.txt 5 ms 256 KB