QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207032 | #7560. Computer Network | ucup-team484# | WA | 1ms | 3532kb | C++17 | 2.3kb | 2023-10-08 03:57:16 | 2023-10-08 03:57:17 |
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 = 64 + __builtin_clzll(b);
else
res = __builtin_clzll(a);
//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<<(63-my_clz(diff));
first_digit = one<<(127-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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3428kb
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: 3460kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
1 249912 43
output:
26
result:
ok 1 number(s): "26"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
2 52522336 155670 52532336 165670
output:
10000
result:
ok 1 number(s): "10000"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
2 141839218 538313890 17731054 67290388
output:
1155
result:
ok 1 number(s): "1155"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
2 678834913 571995689 84855772 71500869
output:
1411
result:
ok 1 number(s): "1411"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3408kb
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: 3532kb
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'