QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#207021 | #7560. Computer Network | ucup-team484# | WA | 0ms | 3876kb | C++17 | 1.7kb | 2023-10-08 03:24:03 | 2023-10-08 03:24:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef long long ll;
typedef pair<int,int> pii;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
cout << "{";
if (sz(v)) print(v[0]);
for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
cout << "}\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<ll> A(N), B(N);
for(int i=0; i<N; i++)
cin >> A[i];
for(int i=0; i<N; i++)
cin >> B[i];
ll res = -1;
for(int k=0; k<33; k++){
ll l = 0, h = 1ll<<62;
for(int i=0; i<N; i++){
ll low = (B[i] << k) - A[i];
ll hi = ((B[i]+1) << k) - 1 - A[i];
l = max(l, low);
h = min(h, hi);
}
//cout << k << ": " << l << " - " << h << endl;
if(l > h)
continue;
ll cur = k;
ll diff, first_digit;
if(l >= (1ll<<(k+1))){
cur += (l>>(k+1)) * 2;
if((l >> (k+1)) != (h >> (k+1))){
l &= (1ll<<(k+1))-1;
if(l <= (1<<k))
cur++;
else
cur += 2;
goto DONE;
}
else{
l &= (1ll<<(k+1))-1;
h &= (1ll<<(k+1))-1;
}
}
//cout << ".. " << l << " -- " << h << ": " << cur << endl;
diff = l ^ h;
if(diff == 0){
}
else{
first_digit = 1ll<<(63-__builtin_clzll(diff));
h &= ~(first_digit-1);
}
cur += __builtin_popcountll(h);
DONE:
//cout << "-> " << cur << endl;
if(res == -1 || cur < res)
res = cur;
}
cout << res << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
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: 3816kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3580kb
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: 3576kb
input:
2 141839218 538313890 17731054 67290388
output:
1155
result:
ok 1 number(s): "1155"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
2 678834913 571995689 84855772 71500869
output:
1411
result:
ok 1 number(s): "1411"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: -100
Wrong Answer
time: 0ms
memory: 3840kb
input:
10 0 74752 70656 67584 29696 44032 80896 22528 1024 52224 2 75 71 68 31 45 81 24 3 53
output:
13
result:
wrong answer 1st numbers differ - expected: '12', found: '13'