QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#318311#7560. Computer NetworknickbelovWA 0ms3876kbC++203.3kb2024-01-31 03:12:022024-01-31 03:12:02

Judging History

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

  • [2024-01-31 03:12:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3876kb
  • [2024-01-31 03:12:02]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(){
    return ostream_iterator<T>(cout," ");
}
template<typename T>
ostream_iterator<T> oit(const string &s){
    return ostream_iterator<T>(cout,s.c_str());
}

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
 
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

constexpr ll NN = 2e5;
constexpr ll M = 1000000007;

ll f1[NN], f2[NN];
ll inv(ll a, ll b = M) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } // inv a mod b
ll choose(ll n, ll k) { return f1[n] * f2[k] % M * f2[n - k] % M; } // n choose k


void run()
{
    ll n,ans=LLONG_MAX; cin >> n; vll a(n),b(n),c(n);
    for(ll &x : a) cin >> x;
    for(ll &x : b) cin >> x;
    

    //let k be number of divs
    auto attempt = [&](ll k){
        ll l=0,r=(1LL<<(k)) - 1;
        for(ll i = 0,x;i<n;i++){
            x = a[i], x>>=k;
            if(x > c[i] || x+1 < c[i])
                return LLONG_MAX;
            ll suff = ((1LL<<(k)) - 1) & a[i];
            if(x < c[i]){
                l = max(l,(1LL<<(k)) - suff); //has to overflow
            }else{
                r = min(r,(1LL<<(k)) - suff - 1); //its not allowed to overflow
            }
        }
        // cout << "\t" << l << " " << r << '\n';
        if(r<l) //impossible
            return LLONG_MAX;

        //find the number from [l,r] with smallest popcount
        ll popc = 0;
        for(ll i = 36;i>=0;i--){
            if(((1LL<<i)&l) == ((1LL<<i)&r)){
                popc+= !!((1LL<<i)&l);
            }else if(i){
                popc++; break;
            }
        }
        
        // cout << k << " " << popc << '\n';

        return k+popc;
    };

    for(ll k = 0;k<=35;k++){
        ll delta = b[0] - (a[0]>>k); //how much smaller
        if(delta <= *ranges::min_element(b) and delta >= 0){
            for(ll i = 0;i<n;i++) c[i]=b[i]-delta;
            ll q = attempt(k);
            if(q != LLONG_MAX) ans = min(ans,q+delta);
        }
        delta = b[0] - ((a[0]>>k) + 1);
        if(delta <= *ranges::min_element(b) and delta>=0){
            for(ll i = 0;i<n;i++) c[i]=b[i]-delta;
            ll q = attempt(k);
            if(q != LLONG_MAX) ans = min(ans,q+delta);
        }
    }

    cout << (ans == LLONG_MAX ? -1 : ans) << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; t=1; while(t--) run();
}

详细

Test #1:

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

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

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

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

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

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

input:

1
249912
43

output:

26

result:

ok 1 number(s): "26"

Test #6:

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

input:

2
52522336 155670
52532336 165670

output:

10000

result:

ok 1 number(s): "10000"

Test #7:

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

input:

2
141839218 538313890
17731054 67290388

output:

1156

result:

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