QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#205059 | #7560. Computer Network | ucup-team859# | WA | 0ms | 3880kb | C++23 | 2.6kb | 2023-10-07 14:44:47 | 2023-10-07 14:44:47 |
Judging History
answer
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
int ans = -1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void back(vector<int> &a, const vector<int> &b, int h = 0) {
int n = (int)a.size();
int df = b[0] - a[0], mx = b[0] - a[0];
for (int i = 1; i < a.size(); ++i) {
if (b[i] - a[i] != df)
df = -1;
mx = max(b[i] - a[i], mx);
if (a[i] - a[i - 1] < b[i] - b[i - 1])
return;
}
/**for (int i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl;
**/
if (df >= 0) {
if (ans == -1)
ans = h + df;
else ans = min(ans, h + df);
cout << ans << endl;
exit(0);
return;
}
if (ans != -1 && h + mx > ans)
return;
//;
vector<int> aux_a = a;
if (rng() & 1) {
for (int i = 0; i < n; ++i) {
a[i] /= 2;
}
back(a, b, h + 1);
a = aux_a;
for (int i = 0; i < n; ++i) {
a[i] = (a[i] + 1) / 2;
}
back(a, b, h + 2);
} else {
for (int i = 0; i < n; ++i) {
a[i] /= 2;
}
back(a, b, h + 1);
a = aux_a;
for (int i = 0; i < n; ++i) {
a[i] = (a[i] + 1) / 2;
}
back(a, b, h + 2);
}
}
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
vector<pair<int, int>> a1;
vector<int> b1;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
/**
for (int i = 0; i < n; ++i) {
a1.push_back({a[i], i});
}
b1 = b;
sort(a1.begin(), a1.end());
sort(b1.begin(), b1.end());
vector<int> b2;
for (int i = 0; i < n; ++i)
b2.push_back(b[a1[i].second]);
if (b1 != b2) {
cout << -1 << endl;
return;
}
b = b1;
for (int i = 0; i < n; ++i)
a[i] = a1[i].first;
**/
back(a, b);
cout << ans << endl;
}
int main() {
#ifdef HOME
ifstream cin("input.in");
ofstream cout("output.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
/**
int t1 = 1;
cout << t1 << endl;
for (int i = 1; i <= t1; ++i) {
int n = 1e6;
cout << n << endl;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; ++i)
a[i] = 1e9 + i;
sort(a.begin(), a.end());
for (int i = 1; i <= n; ++i)
b[i] = 1;
for (int i = 1; i <= n; ++i)
cout << a[i] << " ";
cout << endl;
for (int i = 1; i <= n; ++i)
cout << b[i] << " ";
cout << endl;
}
return 0;
**/
int t = 1;
//cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
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: 3880kb
input:
3 2 3 4 1 2 3
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 65536 65537 1 2
output:
32
result:
ok 1 number(s): "32"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
1 0 28
output:
28
result:
ok 1 number(s): "28"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
1 249912 43
output:
26
result:
ok 1 number(s): "26"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 52522336 155670 52532336 165670
output:
10000
result:
ok 1 number(s): "10000"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
2 141839218 538313890 17731054 67290388
output:
1155
result:
ok 1 number(s): "1155"
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3876kb
input:
2 678834913 571995689 84855772 71500869
output:
-1
result:
wrong answer 1st numbers differ - expected: '1411', found: '-1'