QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #206663 | #7560. Computer Network | ucup-team1264# | TL | 0ms | 3876kb | C++20 | 1.5kb | 2023-10-07 22:06:59 | 2023-10-07 22:07:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define int i64
void solve() {
int n;
cin >> n;
int ans = 1e18;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
for (int d = 0; d < 30; d++) {
int l = 0, r = 1e18;
for (int i = 0; i < n; i++) {
l = max(l, (b[i] << d) - a[i]);
r = min(r, ((b[i] + 1) << d) - 1 - a[i]);
}
if (l > r) continue;
int tmp = 1e18;
if (l >> d == r >> d) {
for (int now = l; now <= r; now += now & (-now)) {
tmp = min(tmp,
d + (now >> d) + popcount(now & ((1ull << d) - 1)));
}
} else {
int mid = (r >> d) << d;
for (int now = l; now < mid; now += now & (-now)) {
tmp = min(tmp,
d + (now >> d) + popcount(now & ((1ull << d) - 1)));
}
for (int now = mid; now <= r; now += now & (-now)) {
tmp = min(tmp,
d + (now >> d) + popcount(now & ((1ull << d) - 1)));
}
}
ans = min(ans, tmp);
}
if (ans >= 1e18) {
cout << -1 << "\n";
} else cout << ans << "\n";
}
#undef int
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
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: 3876kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
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: 3640kb
input:
2 52522336 155670 52532336 165670
output:
10000
result:
ok 1 number(s): "10000"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2 141839218 538313890 17731054 67290388
output:
1155
result:
ok 1 number(s): "1155"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 678834913 571995689 84855772 71500869
output:
1411
result:
ok 1 number(s): "1411"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3524kb
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: 3580kb
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: 3648kb
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: 3804kb
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: 3876kb
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: -100
Time Limit Exceeded
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...