QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224667#7560. Computer NetworkGiga_Cronos#WA 1ms3804kbC++141.5kb2023-10-23 08:10:072023-10-23 08:10:07

Judging History

你现在查看的是最新测评结果

  • [2023-10-23 08:10:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3804kb
  • [2023-10-23 08:10:07]
  • 提交

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'