Submission #10167014
Source Code Expand
Copy
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define F first #define S second #define pb push_back #define pii pair <int, int> #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define reunique(a) (a).resize(unique(all(a)) - (a).begin()) #define ld long double #define int long long int a[200500]; int chk(int mid, int n){ // how much pairs <= mid int ct = 0; for (int i = 0; i < n; i++){ if (a[i] == 0){ if (mid >= 0) ct += n - i - 1; } else{ if (a[i] > 0){ int L = i, R = n; while (R - L > 1){ int MID = (R + L) >> 1; if (a[i] * a[MID] > mid) R = MID; else L = MID; } ct += L - i; } else{ int L = i, R = n; while (R - L > 1){ int MID = (R + L) >> 1; if (a[i] * a[MID] > mid) L = MID; else R = MID; } ct += n - R; } } } return ct; } void SOLVE(){ int n, k; cin >> n >> k; for (int i = 0; i < n; i++){ cin >> a[i]; } sort(a, a + n); int l = -1e18, r = 1e18; while (r - l > 1){ int mid = (r + l) >> 1; if (chk(mid, n) >= k) r = mid; else l = mid; } cout << r << '\n'; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(6); int Q = 1; //cin >> Q; while (Q--){ SOLVE(); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Pairs |
User | Def4ULt |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2082 Byte |
Status | AC |
Exec Time | 774 ms |
Memory | 1792 KB |
Judge Result
Set Name | Sample | Subtask1 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | 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 | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
sub1_01.txt | AC | 277 ms | 896 KB |
sub1_02.txt | AC | 515 ms | 1408 KB |
sub1_03.txt | AC | 750 ms | 1792 KB |
sub1_04.txt | AC | 445 ms | 1152 KB |
sub1_05.txt | AC | 287 ms | 896 KB |
sub1_06.txt | AC | 89 ms | 512 KB |
sub1_07.txt | AC | 531 ms | 1408 KB |
sub1_08.txt | AC | 646 ms | 1664 KB |
sub1_09.txt | AC | 508 ms | 1408 KB |
sub1_10.txt | AC | 113 ms | 512 KB |
sub1_11.txt | AC | 645 ms | 1664 KB |
sub1_12.txt | AC | 73 ms | 512 KB |
sub1_13.txt | AC | 531 ms | 1408 KB |
sub1_14.txt | AC | 232 ms | 768 KB |
sub1_15.txt | AC | 78 ms | 512 KB |
sub1_16.txt | AC | 643 ms | 1664 KB |
sub1_17.txt | AC | 335 ms | 1024 KB |
sub1_18.txt | AC | 30 ms | 384 KB |
sub1_19.txt | AC | 737 ms | 1792 KB |
sub1_20.txt | AC | 427 ms | 1152 KB |
sub1_21.txt | AC | 747 ms | 1792 KB |
sub1_22.txt | AC | 333 ms | 1024 KB |
sub1_23.txt | AC | 373 ms | 1024 KB |
sub1_24.txt | AC | 245 ms | 768 KB |
sub1_25.txt | AC | 152 ms | 640 KB |
sub1_26.txt | AC | 543 ms | 1280 KB |
sub1_27.txt | AC | 27 ms | 1792 KB |
sub1_28.txt | AC | 760 ms | 1792 KB |
sub1_29.txt | AC | 768 ms | 1792 KB |
sub1_30.txt | AC | 770 ms | 1792 KB |
sub1_31.txt | AC | 760 ms | 1792 KB |
sub1_32.txt | AC | 774 ms | 1792 KB |
sub1_33.txt | AC | 760 ms | 1792 KB |
sub1_small_01.txt | AC | 3 ms | 256 KB |
sub1_small_02.txt | AC | 2 ms | 256 KB |
sub1_small_03.txt | AC | 4 ms | 256 KB |
sub1_small_04.txt | AC | 2 ms | 256 KB |
sub1_small_05.txt | AC | 2 ms | 256 KB |
sub1_small_06.txt | AC | 4 ms | 256 KB |
sub1_small_07.txt | AC | 2 ms | 256 KB |
sub1_small_08.txt | AC | 3 ms | 256 KB |
sub1_small_09.txt | AC | 2 ms | 256 KB |
sub1_small_10.txt | AC | 3 ms | 256 KB |
sub1_small_11.txt | AC | 3 ms | 256 KB |
sub1_small_12.txt | AC | 4 ms | 256 KB |
sub1_small_13.txt | AC | 2 ms | 256 KB |
sub1_small_14.txt | AC | 4 ms | 256 KB |
sub1_small_15.txt | AC | 1 ms | 256 KB |
sub1_small_16.txt | AC | 4 ms | 256 KB |
sub1_small_17.txt | AC | 2 ms | 256 KB |
sub1_small_18.txt | AC | 1 ms | 256 KB |
sub1_small_19.txt | AC | 1 ms | 256 KB |
sub1_small_20.txt | AC | 4 ms | 256 KB |
sub1_small_21.txt | AC | 4 ms | 256 KB |
sub1_small_22.txt | AC | 4 ms | 256 KB |
sub1_small_23.txt | AC | 1 ms | 256 KB |
sub1_small_24.txt | AC | 1 ms | 256 KB |
sub1_small_25.txt | AC | 2 ms | 256 KB |
sub1_small_26.txt | AC | 2 ms | 256 KB |
sub1_small_27.txt | AC | 3 ms | 256 KB |
sub1_small_28.txt | AC | 2 ms | 256 KB |
sub1_small_29.txt | AC | 4 ms | 256 KB |
sub1_small_30.txt | AC | 2 ms | 256 KB |
sub1_small_31.txt | AC | 5 ms | 256 KB |
sub1_small_32.txt | AC | 3 ms | 256 KB |
sub1_small_33.txt | AC | 4 ms | 256 KB |
sub1_small_34.txt | AC | 3 ms | 256 KB |
sub1_small_35.txt | AC | 5 ms | 256 KB |
sub1_small_36.txt | AC | 2 ms | 256 KB |
sub1_small_37.txt | AC | 3 ms | 256 KB |
sub1_small_38.txt | AC | 2 ms | 256 KB |
sub1_small_39.txt | AC | 2 ms | 256 KB |
sub1_small_40.txt | AC | 6 ms | 256 KB |
sub1_small_41.txt | AC | 1 ms | 256 KB |
sub1_small_42.txt | AC | 1 ms | 256 KB |
sub1_small_43.txt | AC | 1 ms | 256 KB |