QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224667 | #7560. Computer Network | Giga_Cronos# | WA | 1ms | 3804kb | C++14 | 1.5kb | 2023-10-23 08:10:07 | 2023-10-23 08:10:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fs first
#define sc second
#define pb push_back
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
int qpow(int a,int e,int mod){
if(e==0)return 1;
if(e==1)return a;
if(e%2){
return a*qpow(a,e-1,mod)%mod;
}else{
int c=qpow(a,e/2,mod);
return c*c%mod;
}
}
pii Intersect(pii A,pii B){
if(A>B)swap(A,B);
if(A.sc<B.fs){
return {-1,-1};
}
vi C;
C.pb(A.fs);C.pb(A.sc);C.pb(B.fs);C.pb(B.sc);
sort(all(C));
return {C[1],C[2]};
}
int Descomp(int num,int b){
if(num==0)return 0;
int d=num/(1ll<<b);
return d+Descomp(num-d*(1ll<<b),b-1);
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
vi A(n);
vi B(n);
for(auto &a:A)cin>>a;
for(auto &b:B)cin>>b;
int ans=numeric_limits<int>::max();
for(int i=0;i<=30;i++){
pii R={0,numeric_limits<int>::max()};
for(int j=0;j<n;j++)if(R.fs!=-1){
pii s={B[j]*(1ll<<i),B[j]*(1ll<<i)+(1ll<<i)-1};
s.fs-=A[j];
s.sc-=A[j];
R=Intersect(s,R);
}
if(R.fs==-1)continue;
ans=min(ans,Descomp(R.fs,i)+i);
}
if(ans==numeric_limits<int>::max()){
cout<<-1;
return 0;
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
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: 3636kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3636kb
input:
1 249912 43
output:
32
result:
wrong answer 1st numbers differ - expected: '26', found: '32'