QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318311 | #7560. Computer Network | nickbelov | WA | 0ms | 3876kb | C++20 | 3.3kb | 2024-01-31 03:12:02 | 2024-01-31 03:12:02 |
Judging History
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'