QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#205956 | #7560. Computer Network | ucup-team1055# | WA | 0ms | 3872kb | C++20 | 2.4kb | 2023-10-07 17:56:09 | 2023-10-07 18:00:35 |
Judging History
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'