QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#205956#7560. Computer Networkucup-team1055#WA 0ms3872kbC++202.4kb2023-10-07 17:56:092023-10-07 18:00:35

Judging History

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

  • [2023-10-07 18:00:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3872kb
  • [2023-10-07 17:56:09]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<class T>
bool chmin(T &a, T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template<class T>
bool chmax(T &a, T b) {
    if(a >= b) return false;
    a = b;
    return true;
}

using namespace std;

int main() {
    int n; cin >> n;
    vector<ll> a(n), b(n);
    rep(i,0,n) cin >> a[i];
    rep(i,0,n) cin >> b[i];
    
    vector<ll> ax(n), bx(n);
    rep(i,0,n) ax[i] = (a[i] << 20) + i;
    rep(i,0,n) bx[i] = (b[i] << 20) + i;
    sort(ax.begin(), ax.end());
    sort(bx.begin(), bx.end());
    
    int eron_mask = (1 << 20) - 1;
    bool mode = true;
    rep(i,0,n){
        if ((ax[i] & eron_mask) != (bx[i] & eron_mask)){
            mode = false;
            break;
        }
    }
    if (!mode){
        cout << -1 << '\n';
        return 0;
    }
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector<set<ll>> a0l(31);
    a0l[0].insert(a[0]);
    for (int num=0; num<30; num++){
        for (ll j: a0l[num]){
            a0l[num+1].insert(j/2);
            a0l[num+1].insert((j+1)/2);
        }
    }

    auto min_ppc = [&](ll tlb, ll tub){
        ll ret = 0;
        for (int num=40; num>=0; num--){
            if ((tlb>>num&1) == (tub>>num&1)){
                ret += (tlb>>num&1);
            }else{
                ret += 1;
                break;
            }
        } 
        return ret;
    }; 

    const ll inf = 1e18;
    ll ans = inf;
    for (int num=0; num<31; num++){
        for (ll a0: a0l[num]){
            if (a0 > b[0]) continue;
            ll l = b[0] - a0;
            ll v = 1LL << num;
            // v(l-1) - a[i] < a < vl - a[i]
            ll tlb = 0;
            ll tub = (1LL<<num) - 1;
            rep(i,0,n){
                chmax(tlb, v*(b[i]-l) - a[i]);
                chmin(tub, v*(b[i]-l+1) - a[i]- 1);
            }
            if(tlb > tub) continue;
            ll gr = min_ppc(tlb, tub);
            chmin(ans, gr + l + num);
        }
    }
    if (ans == inf){
        cout << -1 << '\n';
    }else{
        cout << ans << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

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: 3872kb

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

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

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

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

input:

1
249912
43

output:

26

result:

ok 1 number(s): "26"

Test #6:

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

input:

2
52522336 155670
52532336 165670

output:

10000

result:

ok 1 number(s): "10000"

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 3572kb

input:

2
141839218 538313890
17731054 67290388

output:

1156

result:

wrong answer 1st numbers differ - expected: '1155', found: '1156'