QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214997 | #7560. Computer Network | b2ogeyman | WA | 1ms | 3440kb | C++17 | 2.0kb | 2023-10-15 02:03:32 | 2023-10-15 02:03:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ln '\n'
#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 pair<int, int> pii;
typedef vector<int> vi;
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;
bool good = true;
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);
good = true;
rep(i, 0, n) {
a[i] += need*m;
if(a[i] < (b[i] << k))
good = false;
}
cur += need;
if(good) {
ans = min(ans, cur);
} else {
m >>= 1;
int mn = INF, mx = 0;
rep(i, 0, n) {
mn = min(mn, ((b[i]+1) << k) - a[i]);
mx = max(mx, (b[i] << k) - a[i]);
}
while(m) {
if(m < mn) {
mn -= m;
mx -= m;
cur++;
}
good = false;
if(mx <= 0)
good=true;
m >>= 1;
}
}
if(good) {
ans = min(ans, cur + k);
}
}
if(ans == INF)
cout << -1 << ln;
else
cout << ans << ln;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3440kb
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: 1ms
memory: 3400kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3436kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3436kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3372kb
input:
1 249912 43
output:
13
result:
wrong answer 1st numbers differ - expected: '26', found: '13'