QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #705218 | #6693. Fast and Fat | tacmon | AC ✓ | 226ms | 5128kb | C++14 | 1.1kb | 2024-11-02 22:33:51 | 2024-11-02 22:33:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int N, v[maxn], w[maxn];
vector<int> good;
vector<int> bad;
bool check(int mid) {
good.clear(), bad.clear();
for (int i = 1; i <= N; i++) {
if (v[i] < mid) bad.push_back(w[i]);
if (v[i] >= mid) good.push_back(w[i] + v[i] - mid);
}
sort(good.begin(), good.end());
reverse(good.begin(), good.end());
sort(bad.begin(), bad.end());
reverse(bad.begin(), bad.end());
if (bad.size() > good.size()) return false;
int pos = 0;
for (int i = 0; i < (int)bad.size(); i++) {
while (pos + 1 < (int)good.size() && good[pos + 1] >= bad[i]) pos++;
if (pos < i || good[pos] < bad[i]) return false;
}
return true;
}
void solve() {
cin >> N;
for (int i = 1; i <= N; i++) cin >> v[i] >> w[i];
int L = 0, R = 1000000000, res = 0;
while(L <= R) {
int mid = (L + R) >> 1;
if (!check(mid)) R = mid - 1;
else res = mid, L = mid + 1;
}
printf("%d\n", res);
}
int main() {
// freopen("a.in", "r", stdin);
int T = 0;
cin >> T;
while(T--) solve();
return 0;
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
2 5 10 5 1 102 10 100 7 4 9 50 2 1 100 10 1
output:
8 1
result:
ok 2 number(s): "8 1"
Test #2:
score: 0
Accepted
time: 70ms
memory: 3912kb
input:
10000 4 280251502 664541723 375808746 641141991 95134537 898607509 455259328 944978891 2 798417052 547329847 785434740 991778535 6 623628702 857611223 275667427 453747403 292209526 283132767 330752033 988721243 470297536 608192332 477186035 325224271 3 280572174 994054447 306566740 923535026 3781360...
output:
352409014 785434740 470297536 280572174 704877362 960871619 691253609 560579095 136979645 399988835 610497257 576427565 636500913 315900406 370430730 526259135 781258283 631916852 300930080 419999540 431930706 479323438 530080165 391912906 708925499 467782812 457987604 389750718 447390353 696516804 ...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 100ms
memory: 3892kb
input:
400 908 33362229 606508747 632419478 324326751 257284260 336303174 457246243 986284341 542591728 520499949 519145521 971093641 633038285 374866966 137832222 929747560 626840805 488847915 750542462 328721976 928847956 932651817 479954326 140789806 794986794 212084514 372002273 933710809 173161453 119...
output:
504394967 484359492 469225546 475096879 595868798 497700736 456321846 407898878 591377003 568847769 747288891 512226022 532505353 472511102 511795703 477459477 529231318 472548529 525635770 487622149 510138466 527879972 504505269 498990235 475265402 514165957 449627768 450001628 349076692 507182026 ...
result:
ok 400 numbers
Test #4:
score: 0
Accepted
time: 199ms
memory: 4152kb
input:
10 20711 764663709 192212865 55777289 890465487 406536728 278177638 204765968 477730025 379283253 654167175 41026104 774138002 875860206 465532238 934199361 38168843 545038187 933648246 99831648 715642411 984100235 592340109 870539197 676140250 2503522 500646009 813801461 79167382 531368117 16295473...
output:
499001302 509703433 508081053 500768234 505503494 508790115 506879049 472330839 499777658 493607522
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 201ms
memory: 4320kb
input:
5 28172 644161572 775630724 644996423 77402453 959618325 764663709 192212865 55777289 890465487 406536728 278177638 204765968 477730025 379283253 654167175 41026104 774138002 875860206 465532238 934199361 38168843 545038187 933648246 99831648 715642411 984100235 592340109 870539197 676140250 2503522...
output:
500467154 499019830 502230846 506222919 497700052
result:
ok 5 number(s): "500467154 499019830 502230846 506222919 497700052"
Test #6:
score: 0
Accepted
time: 226ms
memory: 4752kb
input:
1 100000 288393588 839718077 938561398 470676893 644161572 775630724 644996423 77402453 959618325 764663709 192212865 55777289 890465487 406536728 278177638 204765968 477730025 379283253 654167175 41026104 774138002 875860206 465532238 934199361 38168843 545038187 933648246 99831648 715642411 984100...
output:
501283249
result:
ok 1 number(s): "501283249"
Test #7:
score: 0
Accepted
time: 45ms
memory: 3916kb
input:
10000 4 2 23 46 91 37 9 28 91 2 52 47 40 35 6 2 23 27 3 26 67 33 43 36 32 35 71 3 74 47 40 26 5 35 29 8 16 88 78 16 72 45 68 31 74 59 35 48 10 88 9 46 43 85 28 19 77 62 29 21 28 95 6 84 98 65 36 90 5 29 86 65 2 20 36 9 31 5 52 71 95 26 28 87 48 48 58 24 60 42 92 90 81 2 58 94 19 63 4 24 66 11 82 9 7...
output:
28 52 33 40 45 58 19 47 45 55 30 41 53 61 6 34 11 52 73 48 40 58 57 28 65 46 41 49 53 45 50 51 53 61 62 55 72 65 56 51 4 47 19 31 39 84 66 58 58 85 50 37 45 35 37 54 62 56 82 40 61 13 42 40 32 70 51 77 44 38 86 35 48 21 86 64 50 44 62 62 35 40 49 66 27 12 47 54 70 66 44 58 70 47 70 28 80 58 57 68 61...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 64ms
memory: 3960kb
input:
400 908 29 47 78 51 60 74 43 41 28 49 21 41 85 66 22 60 5 15 62 76 56 17 26 6 94 14 73 9 53 7 71 9 68 94 57 85 89 1 71 74 19 66 70 41 77 25 26 29 93 33 25 50 86 23 5 4 59 21 98 38 26 97 34 99 54 11 24 96 93 22 61 88 94 76 50 99 20 89 44 59 17 49 83 6 60 3 12 26 92 70 90 40 2 20 100 70 63 49 1 81 20 ...
output:
50 52 51 51 49 46 53 50 50 55 51 52 53 50 55 46 48 54 52 50 51 53 54 51 48 46 53 52 45 55 48 58 52 54 50 53 45 53 59 47 49 48 53 48 56 57 53 49 55 39 51 50 55 50 46 45 48 58 49 57 37 61 49 46 55 57 41 48 54 45 43 53 50 51 51 54 49 47 51 51 42 47 50 58 54 44 46 53 48 52 50 49 52 54 50 80 50 55 46 50 ...
result:
ok 400 numbers
Test #9:
score: 0
Accepted
time: 115ms
memory: 4200kb
input:
10 20711 9 65 89 87 28 38 68 25 53 75 4 2 6 38 61 43 87 46 48 11 35 9 97 50 22 9 61 82 17 36 100 41 48 62 68 20 84 71 92 89 14 18 6 51 42 80 38 89 93 15 72 19 91 11 42 77 69 8 16 81 5 82 82 81 1 24 90 91 16 66 15 23 49 43 51 89 6 7 14 80 42 6 32 92 39 55 31 5 64 93 7 98 13 26 44 31 50 39 71 71 72 58...
output:
50 51 51 50 50 48 51 48 50 50
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 118ms
memory: 4240kb
input:
5 28172 72 24 23 53 25 9 65 89 87 28 38 68 25 53 75 4 2 6 38 61 43 87 46 48 11 35 9 97 50 22 9 61 82 17 36 100 41 48 62 68 20 84 71 92 89 14 18 6 51 42 80 38 89 93 15 72 19 91 11 42 77 69 8 16 81 5 82 82 81 1 24 90 91 16 66 15 23 49 43 51 89 6 7 14 80 42 6 32 92 39 55 31 5 64 93 7 98 13 26 44 31 50 ...
output:
50 50 51 50 50
result:
ok 5 number(s): "50 50 51 50 50"
Test #11:
score: 0
Accepted
time: 116ms
memory: 5084kb
input:
1 100000 88 77 98 93 72 24 23 53 25 9 65 89 87 28 38 68 25 53 75 4 2 6 38 61 43 87 46 48 11 35 9 97 50 22 9 61 82 17 36 100 41 48 62 68 20 84 71 92 89 14 18 6 51 42 80 38 89 93 15 72 19 91 11 42 77 69 8 16 81 5 82 82 81 1 24 90 91 16 66 15 23 49 43 51 89 6 7 14 80 42 6 32 92 39 55 31 5 64 93 7 98 13...
output:
50
result:
ok 1 number(s): "50"
Test #12:
score: 0
Accepted
time: 67ms
memory: 3844kb
input:
10000 4 2 664541723 46 641141991 37 898607509 28 944978891 2 52 547329847 40 991778535 6 2 857611223 27 453747403 26 283132767 33 988721243 36 608192332 35 325224271 3 74 994054447 40 923535026 5 968172335 29 8 305218916 88 728428678 16 772370072 45 470855168 31 812837974 59 942468735 48 355798010 8...
output:
28 40 33 40 48 19 11 10 45 35 18 11 52 6 2 19 6 31 61 48 6 58 40 20 6 39 41 7 53 4 50 22 53 43 37 55 49 6 29 47 13 18 19 24 39 84 64 44 66 85 39 37 38 24 46 62 62 31 81 11 62 13 3 56 27 68 30 77 40 26 86 12 23 81 22 40 11 44 17 48 35 34 41 39 27 18 29 50 70 66 25 49 54 21 70 21 80 53 57 55 53 13 16 ...
result:
ok 10000 numbers
Test #13:
score: 0
Accepted
time: 79ms
memory: 3884kb
input:
400 908 29 606508747 78 324326751 60 336303174 43 986284341 28 520499949 21 971093641 85 374866966 22 929747560 5 488847915 62 328721976 56 932651817 26 140789806 94 212084514 73 933710809 53 119826107 71 909724309 68 7512494 57 599004185 89 162704201 71 683914474 19 580976366 70 89178341 77 4509518...
output:
33 9 37 20 36 15 48 48 44 27 42 50 33 48 7 37 20 50 52 37 12 50 42 14 40 4 17 30 7 53 42 51 45 33 27 36 27 2 30 47 41 24 23 12 18 55 5 33 47 41 37 25 52 23 27 28 24 40 26 57 31 4 28 22 48 36 31 47 53 42 34 52 17 51 49 43 43 6 51 5 5 28 28 37 26 7 34 44 26 42 42 32 33 1 41 70 16 43 11 15 8 43 30 21 3...
result:
ok 400 numbers
Test #14:
score: 0
Accepted
time: 181ms
memory: 4160kb
input:
10 20711 9 192212865 89 890465487 28 278177638 68 477730025 53 654167175 4 774138002 6 465532238 61 38168843 87 933648246 48 715642411 35 592340109 97 676140250 22 500646009 61 79167382 17 162954736 100 580544241 48 676203262 68 315195920 84 130115971 92 798706989 14 638007218 6 1801751 42 562962580...
output:
38 48 12 15 27 33 49 6 30 42
result:
ok 10 numbers
Test #15:
score: 0
Accepted
time: 188ms
memory: 4152kb
input:
5 28172 72 775630724 23 77402453 25 764663709 65 55777289 87 406536728 38 204765968 25 379283253 75 41026104 2 875860206 38 934199361 43 545038187 46 99831648 11 984100235 9 870539197 50 2503522 9 813801461 82 531368117 36 799855000 41 682379648 62 981783468 20 686172784 71 953975592 89 237758314 18...
output:
12 18 46 50 26
result:
ok 5 number(s): "12 18 46 50 26"
Test #16:
score: 0
Accepted
time: 211ms
memory: 5128kb
input:
1 100000 88 839718077 98 470676893 72 775630724 23 77402453 25 764663709 65 55777289 87 406536728 38 204765968 25 379283253 75 41026104 2 875860206 38 934199361 43 545038187 46 99831648 11 984100235 9 870539197 50 2503522 9 813801461 82 531368117 36 799855000 41 682379648 62 981783468 20 686172784 7...
output:
18
result:
ok 1 number(s): "18"
Test #17:
score: 0
Accepted
time: 63ms
memory: 3796kb
input:
10000 4 280251502 23 375808746 91 95134537 9 455259328 91 2 798417052 47 785434740 35 6 623628702 23 275667427 3 292209526 67 330752033 43 470297536 32 477186035 71 3 280572174 47 306566740 26 37813605 35 29 810469108 16 468608188 78 827457716 72 802358145 68 314367531 74 433130259 35 990797348 10 6...
output:
375808746 798417052 470297536 280572174 704877362 960871588 691253609 560579095 136979645 399988835 724307800 576427565 640092473 315900406 550838706 526259135 921220111 631916852 300930080 419999540 667381564 479323438 530080165 493047741 708925499 509158939 457987604 389750718 447390353 696516804 ...
result:
ok 10000 numbers
Test #18:
score: 0
Accepted
time: 86ms
memory: 3828kb
input:
400 908 33362229 47 632419478 51 257284260 74 457246243 41 542591728 49 519145521 41 633038285 66 137832222 60 626840805 15 750542462 76 928847956 17 479954326 6 794986794 14 372002273 9 173161453 7 967568271 9 284795668 94 275846657 85 471944589 1 246318671 74 331934519 66 485330370 41 859606377 25...
output:
504394967 484359492 469225546 475096879 595868798 497700736 456321846 407898878 591377003 568847769 747288891 512226022 532505353 472511102 511795703 477459477 529231318 472548529 525635770 487622149 510138466 527879972 504505269 498990235 475265402 514165957 449627768 450001628 349076692 507182026 ...
result:
ok 400 numbers
Test #19:
score: 0
Accepted
time: 160ms
memory: 4108kb
input:
10 20711 764663709 65 55777289 87 406536728 38 204765968 25 379283253 75 41026104 2 875860206 38 934199361 43 545038187 46 99831648 11 984100235 9 870539197 50 2503522 9 813801461 82 531368117 36 799855000 41 682379648 62 981783468 20 686172784 71 953975592 89 237758314 18 598269306 51 149834242 80 ...
output:
499001302 509703433 508081053 500768234 505503494 508790115 506879049 472330839 499777658 493607522
result:
ok 10 numbers
Test #20:
score: 0
Accepted
time: 162ms
memory: 4388kb
input:
5 28172 644161572 24 644996423 53 959618325 9 192212865 89 890465487 28 278177638 68 477730025 53 654167175 4 774138002 6 465532238 61 38168843 87 933648246 48 715642411 35 592340109 97 676140250 22 500646009 61 79167382 17 162954736 100 580544241 48 676203262 68 315195920 84 130115971 92 798706989 ...
output:
500467154 499019830 502230846 506222919 497700052
result:
ok 5 number(s): "500467154 499019830 502230846 506222919 497700052"
Test #21:
score: 0
Accepted
time: 169ms
memory: 4808kb
input:
1 100000 288393588 77 938561398 93 644161572 24 644996423 53 959618325 9 192212865 89 890465487 28 278177638 68 477730025 53 654167175 4 774138002 6 465532238 61 38168843 87 933648246 48 715642411 35 592340109 97 676140250 22 500646009 61 79167382 17 162954736 100 580544241 48 676203262 68 315195920...
output:
501283249
result:
ok 1 number(s): "501283249"