Submission #46749950
Source Code Expand
Copy
#include <stdio.h>#include <stdlib.h>int cmp(const void* x, const void* y) {int a = *(const int*)x, b = *(const int*)y;return a < b ? -1 : a > b;}int N, M;int A[212345];int B[212345];/* A_i 円以上なら売る → A_i が小さいほど売ってもらいやすい */int get_urite(int x) {int yes = 0, no = N - 1;if (x < A[0]) return 0;if (A[N - 1] <= x) return N;while (yes + 1 < no) {int m = yes + (no - yes) / 2;if (A[m] <= x) yes = m; else no = m;}
#include <stdio.h> #include <stdlib.h> int cmp(const void* x, const void* y) { int a = *(const int*)x, b = *(const int*)y; return a < b ? -1 : a > b; } int N, M; int A[212345]; int B[212345]; /* A_i 円以上なら売る → A_i が小さいほど売ってもらいやすい */ int get_urite(int x) { int yes = 0, no = N - 1; if (x < A[0]) return 0; if (A[N - 1] <= x) return N; while (yes + 1 < no) { int m = yes + (no - yes) / 2; if (A[m] <= x) yes = m; else no = m; } return yes + 1; } /* B_i 円以下なら買う → B_i が大きいほど買ってもらいやすい */ int get_kaite(int x) { int no = 0, yes = M - 1; if (B[M - 1] < x) return 0; if (x <= B[0]) return M; while (no + 1 < yes) { int m = no + (yes - no) / 2; if (x <= B[m]) yes = m; else no = m; } return M - yes; } int main(void) { int i; int no = 0, yes = 1010101010; if (scanf("%d%d", &N, &M) != 2) return 1; for (i = 0; i < N; i++) { if (scanf("%d", &A[i]) != 1) return 1; } for (i = 0; i < M; i++) { if (scanf("%d", &B[i]) != 1) return 1; } qsort(A, N, sizeof(*A), cmp); qsort(B, M, sizeof(*B), cmp); while (no + 1 < yes) { int m = no + (yes - no) / 2; if (get_urite(m) >= get_kaite(m)) yes = m; else no = m; } printf("%d\n", yes); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Invisible Hand |
User | mikecat |
Language | C (gcc 12.2.0) |
Score | 300 |
Code Size | 1321 Byte |
Status | AC |
Exec Time | 82 ms |
Memory | 3980 KiB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, random_41.txt, sample_01.txt, sample_02.txt, sample_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
random_01.txt | AC | 82 ms | 3980 KiB |
random_02.txt | AC | 81 ms | 3944 KiB |
random_03.txt | AC | 77 ms | 3748 KiB |
random_04.txt | AC | 66 ms | 3464 KiB |
random_05.txt | AC | 82 ms | 3940 KiB |
random_06.txt | AC | 54 ms | 3148 KiB |
random_07.txt | AC | 47 ms | 3108 KiB |
random_08.txt | AC | 64 ms | 3424 KiB |
random_09.txt | AC | 82 ms | 3968 KiB |
random_10.txt | AC | 73 ms | 3476 KiB |
random_11.txt | AC | 52 ms | 3088 KiB |
random_12.txt | AC | 68 ms | 3624 KiB |
random_13.txt | AC | 27 ms | 2820 KiB |
random_14.txt | AC | 10 ms | 2016 KiB |
random_15.txt | AC | 27 ms | 2880 KiB |
random_16.txt | AC | 46 ms | 3256 KiB |
random_17.txt | AC | 18 ms | 2304 KiB |
random_18.txt | AC | 35 ms | 2960 KiB |
random_19.txt | AC | 38 ms | 2984 KiB |
random_20.txt | AC | 40 ms | 2828 KiB |
random_21.txt | AC | 10 ms | 2040 KiB |
random_22.txt | AC | 24 ms | 2332 KiB |
random_23.txt | AC | 52 ms | 3348 KiB |
random_24.txt | AC | 36 ms | 2756 KiB |
random_25.txt | AC | 19 ms | 3016 KiB |
random_26.txt | AC | 6 ms | 2144 KiB |
random_27.txt | AC | 5 ms | 2004 KiB |
random_28.txt | AC | 22 ms | 3264 KiB |
random_29.txt | AC | 6 ms | 2064 KiB |
random_30.txt | AC | 4 ms | 1860 KiB |
random_31.txt | AC | 12 ms | 2432 KiB |
random_32.txt | AC | 24 ms | 3324 KiB |
random_33.txt | AC | 24 ms | 3240 KiB |
random_34.txt | AC | 0 ms | 1636 KiB |
random_35.txt | AC | 0 ms | 1652 KiB |
random_36.txt | AC | 1 ms | 1580 KiB |
random_37.txt | AC | 0 ms | 1580 KiB |
random_38.txt | AC | 0 ms | 1628 KiB |
random_39.txt | AC | 0 ms | 1644 KiB |
random_40.txt | AC | 0 ms | 1716 KiB |
random_41.txt | AC | 0 ms | 1640 KiB |
sample_01.txt | AC | 1 ms | 1644 KiB |
sample_02.txt | AC | 1 ms | 1704 KiB |
sample_03.txt | AC | 0 ms | 1568 KiB |