QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214938 | #7560. Computer Network | b2ogeyman | WA | 1ms | 3448kb | C++17 | 1.9kb | 2023-10-15 01:34:56 | 2023-10-15 01:34:56 |
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;
bool good = true;
while(m) {
int need = 0;
if(m == (1LL << k)) {
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);
}
need = min(need1, need2);
} else {
need = 1;
rep(i, 0, n) {
if(a[i] + m >= ((b[i]+1) << k)) {
need = 0;
break;
}
}
}
good = true;
rep(i, 0, n) {
a[i] += need*m;
if(a[i] < (b[i] << k))
good=false;
}
cur += need;
if(good)
break;
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: 3436kb
input:
5 1 2 3 4 5 6 6 6 6 7
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3448kb
input:
3 2 3 4 1 2 3
output:
31
result:
wrong answer 1st numbers differ - expected: '-1', found: '31'