QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214927 | #7560. Computer Network | b2ogeyman | TL | 4ms | 3708kb | C++17 | 1.6kb | 2023-10-15 01:29:03 | 2023-10-15 01:29:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define ln '\n'
#define int ll
const int INF = 1e9+7;
int n;
vi a, aa, b;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
a.resize(n);
aa.resize(n);
b.resize(n);
rep(i, 0, n)
cin >> aa[i];
rep(i, 0, n)
cin >> b[i];
int ans = INF;
rep(k, 0, 32) {
rep(i, 0, n)
a[i] = aa[i];
bool flag = false;
rep(i, 0, n)
if(a[i] >= (b[i]+1)*(1LL << k))
flag = true;
if(flag)
continue;
int m = (1LL << k);
int cur = 0;
while(m) {
int need1 = INF, need2 = 0;
rep(i, 0, n) {
need1 = min(need1, max(0LL, (b[i]*(1LL << k) + (1LL << k) - 1 - a[i]))/m);
need2 = max(need2, max(0LL, (b[i]*(1LL << k) + m - 1 - a[i]))/m);
}
int need = min(need1, need2);
rep(i, 0, n)
a[i] += need*m;
cur += need;
m >>= 1;
}
bool good = true;
rep(i, 0, n) {
assert(a[i] < (b[i]+1)*(1LL << k));
if(a[i] < b[i]*(1LL << k))
good=false;
}
if(good)
ans = min(ans, cur + k);
}
if(ans == INF)
cout << -1 << ln;
else
cout << ans << ln;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
5 1 2 3 4 5 6 6 6 6 7
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1 249912 43
output:
26
result:
ok 1 number(s): "26"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 52522336 155670 52532336 165670
output:
10000
result:
ok 1 number(s): "10000"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 141839218 538313890 17731054 67290388
output:
1155
result:
ok 1 number(s): "1155"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 678834913 571995689 84855772 71500869
output:
1411
result:
ok 1 number(s): "1411"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
10 66 0 65 10 40 1 44 29 13 15 84 18 83 28 58 19 62 47 31 33
output:
18
result:
ok 1 number(s): "18"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
10 0 74752 70656 67584 29696 44032 80896 22528 1024 52224 2 75 71 68 31 45 81 24 3 53
output:
12
result:
ok 1 number(s): "12"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
10 216 232 28 340 0 44 212 172 268 60 59 63 12 90 5 16 58 48 72 20
output:
7
result:
ok 1 number(s): "7"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
10 31 36 17 0 61 25 66 0 74 56 47 52 33 16 77 41 82 16 90 72
output:
16
result:
ok 1 number(s): "16"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
10 17 6 41 68 34 46 32 64 24 0 36 25 60 87 53 65 51 83 43 19
output:
19
result:
ok 1 number(s): "19"
Test #14:
score: 0
Accepted
time: 4ms
memory: 3600kb
input:
1000 403 162 111 73 964 795 667 191 80 204 250 672 907 603 523 804 203 729 21 717 788 916 570 41 811 990 730 61 376 162 972 288 12 859 935 290 178 657 199 143 634 417 43 980 232 143 27 669 676 699 215 96 690 293 419 522 841 774 31 875 481 365 402 312 773 882 478 758 345 970 558 174 997 272 557 201 6...
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
1000 286261248 131596288 375914496 430964736 134217728 105381888 484966400 195559424 458752000 325058560 261095424 261095424 396361728 117964800 408420352 285212672 230162432 180355072 356515840 461373440 216006656 489160704 287834112 77594624 314572800 217579520 381157376 456654848 209715200 734003...
output:
19
result:
ok 1 number(s): "19"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
1000 332922880 109576192 244318208 244842496 347078656 56623104 56098816 87556096 152043520 115343360 170393600 521666560 198180864 252182528 272629760 408944640 368050176 341311488 257949696 264765440 40370176 478150656 343932928 491257856 13107200 400556032 281018368 284688384 132120576 119537664 ...
output:
19
result:
ok 1 number(s): "19"
Test #17:
score: 0
Accepted
time: 3ms
memory: 3604kb
input:
1000 303104 489984 55808 445952 470528 328192 461312 297984 275456 354816 88064 495104 324096 112640 386560 201728 184320 236544 239104 86016 28160 9728 227328 184832 190976 113152 286208 201728 57856 263168 502272 402944 219136 475136 283648 368128 371712 190464 205824 223744 304640 378368 64512 45...
output:
10
result:
ok 1 number(s): "10"
Test #18:
score: 0
Accepted
time: 4ms
memory: 3632kb
input:
1000 1364 2404 2060 3112 404 1740 2672 732 1456 2168 3176 896 1492 1828 72 212 688 1752 528 592 2060 3232 3476 2840 728 980 240 2428 3008 2688 2736 1372 956 3320 3680 0 3176 2312 1688 688 3244 2076 136 148 572 968 3724 3456 2404 3688 3176 668 92 788 2328 3748 1204 1696 980 2944 824 1224 308 1752 250...
output:
3
result:
ok 1 number(s): "3"
Test #19:
score: 0
Accepted
time: 4ms
memory: 3636kb
input:
1000 24 97 280 132 651 154 514 816 474 145 764 333 411 643 961 975 68 100 404 21 791 749 463 241 818 555 178 219 654 980 367 149 481 19 814 609 146 995 898 703 352 663 215 155 64 672 310 347 730 32 134 782 247 195 785 367 152 429 800 145 718 190 268 220 545 138 522 606 143 198 426 526 236 669 396 32...
output:
2
result:
ok 1 number(s): "2"
Test #20:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
1000 252706816 405274624 406847488 451936256 322961408 365953024 288882688 402128896 427819008 70778880 268435456 1572864 417857536 8388608 499122176 399507456 240648192 197132288 331874304 278921216 469237760 249561088 393216000 81264640 271581184 453509120 124780544 417857536 114819072 30408704 24...
output:
20
result:
ok 1 number(s): "20"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1000 81264640 139460608 264241152 432013312 266862592 383778816 262144000 56098816 421003264 461373440 434110464 202375168 87556096 341311488 200802304 78643200 44040192 500695040 258473984 516423680 508559360 58195968 347078656 262668288 247988224 482869248 426246144 188743680 154140672 385875968 4...
output:
22
result:
ok 1 number(s): "22"
Test #22:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
1000 342360064 339214336 246939648 378535936 286785536 19398656 102760448 51904512 290455552 104857600 112721920 214433792 423100416 230686720 406847488 408944640 165675008 245366784 498597888 373817344 135266304 14680064 190840832 425721856 279969792 262668288 199229440 230686720 511705088 51694796...
output:
19
result:
ok 1 number(s): "19"
Test #23:
score: 0
Accepted
time: 3ms
memory: 3572kb
input:
1000 196096 493056 187392 207872 254976 194048 94720 433664 445952 299520 300544 203776 303616 424960 206848 4608 91136 472576 346112 179712 268288 192512 164352 445952 56832 33792 233984 60928 114688 95232 289792 340992 107520 87040 498688 108032 263680 423424 305152 179200 330240 26112 163328 3676...
output:
9
result:
ok 1 number(s): "9"
Test #24:
score: -100
Time Limit Exceeded
input:
1000000 788529152 41943040 444596224 603979776 830472192 50331648 687865856 159383552 16777216 813694976 427819008 528482304 310378496 452984832 402653184 218103808 117440512 226492416 796917760 570425344 301989888 360710144 553648128 746586112 41943040 536870912 343932928 528482304 285212672 192937...