QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#207030 | #7560. Computer Network | ucup-team484# | WA | 0ms | 3632kb | C++17 | 2.3kb | 2023-10-08 03:54:01 | 2023-10-08 03:54:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef __int128 ll;
//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";
}
ll one = 1;
ll my_popcount(ll x){
unsigned long long a = x>>64;
unsigned long long b = x & ((one << 64)-1);
ll res = __builtin_popcountll(a) + __builtin_popcountll(b);
//assert(res == __builtin_popcountll(x));
return res;
}
ll my_clz(ll x){
unsigned long long a = x>>64;
unsigned long long b = x & ((one << 64)-1);
ll res;
if(a == 0)
res = __builtin_clzll(a);
else
res = 64 + __builtin_clzll(b);
//assert(res == __builtin_clzll(x));
return res;
}
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++){
int x;
cin >> x;
A[i] = x;
}
for(int i=0; i<N; i++){
int x;
cin >> x;
B[i] = x;
}
//print(A);
//print(B);
ll res = -1;
for(int k=0; k<80; k++){
ll l = 0, h = one<<120;
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 << l << "," << h << " ";
}
//cout << endl;
//cout << k << ": " << l << " - " << h << endl;
if(l > h)
continue;
ll cur = k;
ll diff, first_digit;
if(l >= (one<<(k+1))){
cur += (l>>(k+1)) * 2;
if((l >> (k+1)) != (h >> (k+1))){
l &= (one<<(k+1))-1;
if(l <= (one<<k))
cur++;
else
cur += 2;
goto DONE;
}
else{
l &= (one<<(k+1))-1;
h &= (one<<(k+1))-1;
}
}
//cout << ".. " << l << " -- " << h << ": " << cur << endl;
diff = l ^ h;
if(diff == 0){
}
else{
//first_digit = 1ll<<(64-my_clz(diff));
first_digit = one<<(128-my_clz(diff));
h &= ~(first_digit-1);
}
cur += my_popcount(h);
DONE:
//cout << "-> " << cur << endl;
if(res == -1 || cur < res)
res = cur;
}
cout << (long long) res << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
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: 3584kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3528kb
input:
1 249912 43
output:
25
result:
wrong answer 1st numbers differ - expected: '26', found: '25'