QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204487#7560. Computer Networkucup-team1631#WA 1ms3480kbC++202.4kb2023-10-07 12:06:582023-10-07 12:06:59

Judging History

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

  • [2023-10-07 12:06:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3480kb
  • [2023-10-07 12:06:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#include <time.h> 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
#define all(A) A.begin(),A.end()
#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)
template<class T>
bool chmax(T& p, T q, bool C = 1) {
    if (C == 0 && p == q) {
        return 1;
    }
    if (p < q) {
        p = q;
        return 1;
    }
    else {
        return 0;
    }
}
template<class T>
bool chmin(T& p, T q, bool C = 1) {
    if (C == 0 && p == q) {
        return 1;
    }
    if (p > q) {
        p = q;
        return 1;
    }
    else {
        return 0;
    }
}

ll minpopcnt(ll L,ll R){
    ll res=0;
    for(ll i=32;i>=0;i--){
        if(R&(1ll<<i)){
            if(L&(1ll<<i)){
                res++;
            }
            else{
                return res;
            }
        }
    }
    return res;
}

bool DEB=0;
int main() {
    ll N;
    cin >> N;
    vll A(N), B(N);
    vector<pair<ll, ll>> P(N);
    rep(i, N)cin >> A[i];
    rep(i, N) {
        cin >> B[i];
        P[i] = { B[i],A[i] };
    }
    /*
    sort(all(P));
    rep(i,N-1){
        if(P[i].first<P[i+1].first){
            if(P[i].second>=P[i+1].second){
                cout<<-1<<endl;
                return 0;
            }
        }
    }*/
    ll an = 1e18;
    for (ll i = 0; i <= 31; i++) {
        
        rep(t, 2) {
            ll R = (1ll << i) - 1, L = 0;
            ll g;
            if (t == 0) {
                g = B[0] - (A[0] / (1ll << i));
            }
            else {
                g = B[0] - (A[0] / (1ll << i) + 1);
            }
            if (g < 0)continue;
            bool OK = 1;
            rep(n, N) {
                ll a = A[n];
                ll b = B[n] - g;
                if (b > a) {
                    OK = 0;
                    break;
                }
                //(a+x)//(1ll<<i)==b-g
                chmax(L, b * (1ll << i) - a);
                chmin(R, b * (1ll << i) + (1ll << i) - 1 - a);
            }
            if (!OK)continue;
            if (L > R)continue;
            if(DEB)cout << i << " " << g << " " << L << " " << R << endl;
            chmin(an, i + g + minpopcnt(L,R));
        }
    }
    if (an > 1e15)cout << -1 << endl;
    else cout << an << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3416kb

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: 1ms
memory: 3480kb

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3388kb

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3480kb

input:

1
249912
43

output:

25

result:

wrong answer 1st numbers differ - expected: '26', found: '25'