QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#204487 | #7560. Computer Network | ucup-team1631# | WA | 1ms | 3480kb | C++20 | 2.4kb | 2023-10-07 12:06:58 | 2023-10-07 12:06:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <time.h>
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
#define all(A) A.begin(),A.end()
#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)
template<class T>
bool chmax(T& p, T q, bool C = 1) {
if (C == 0 && p == q) {
return 1;
}
if (p < q) {
p = q;
return 1;
}
else {
return 0;
}
}
template<class T>
bool chmin(T& p, T q, bool C = 1) {
if (C == 0 && p == q) {
return 1;
}
if (p > q) {
p = q;
return 1;
}
else {
return 0;
}
}
ll minpopcnt(ll L,ll R){
ll res=0;
for(ll i=32;i>=0;i--){
if(R&(1ll<<i)){
if(L&(1ll<<i)){
res++;
}
else{
return res;
}
}
}
return res;
}
bool DEB=0;
int main() {
ll N;
cin >> N;
vll A(N), B(N);
vector<pair<ll, ll>> P(N);
rep(i, N)cin >> A[i];
rep(i, N) {
cin >> B[i];
P[i] = { B[i],A[i] };
}
/*
sort(all(P));
rep(i,N-1){
if(P[i].first<P[i+1].first){
if(P[i].second>=P[i+1].second){
cout<<-1<<endl;
return 0;
}
}
}*/
ll an = 1e18;
for (ll i = 0; i <= 31; i++) {
rep(t, 2) {
ll R = (1ll << i) - 1, L = 0;
ll g;
if (t == 0) {
g = B[0] - (A[0] / (1ll << i));
}
else {
g = B[0] - (A[0] / (1ll << i) + 1);
}
if (g < 0)continue;
bool OK = 1;
rep(n, N) {
ll a = A[n];
ll b = B[n] - g;
if (b > a) {
OK = 0;
break;
}
//(a+x)//(1ll<<i)==b-g
chmax(L, b * (1ll << i) - a);
chmin(R, b * (1ll << i) + (1ll << i) - 1 - a);
}
if (!OK)continue;
if (L > R)continue;
if(DEB)cout << i << " " << g << " " << L << " " << R << endl;
chmin(an, i + g + minpopcnt(L,R));
}
}
if (an > 1e15)cout << -1 << endl;
else cout << an << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3416kb
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: 3480kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3388kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3480kb
input:
1 249912 43
output:
25
result:
wrong answer 1st numbers differ - expected: '26', found: '25'