QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#802739 | #9832. If I Could Turn Back Time | ucup-team3723# | WA | 0ms | 3740kb | C++20 | 2.6kb | 2024-12-07 14:33:29 | 2024-12-07 14:33:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(v) v.begin(),v.end()
#define dbg(x) cerr << #x << ": " << (x) << endl;
mt19937 rnd;
int n;
vector<int> h,p;
void input() {
cin >> n;
h.resize(n);
p.resize(n);
for (int i = 0; i < n; ++i) cin >> h[i];
for (int i = 0; i < n; ++i) cin >> p[i];
}
void gen() {
n = 5;
h.resize(n);
p.resize(n);
for (int i = 0; i < n; ++i) h[i] = rnd() % 10;
// sort(ALL(h));
for (int i = 0; i < n; ++i) p[i] = rnd() % 10 + h[i];
}
int naive() {
int cnt = 0;
for (int i = 0; i < n; ++i) if (p[i] < h[i]) return -1;
while (true) {
int idx = 1e9;
for (int i = 0; i < n; ++i) if (p[i] > h[i]) {
if (idx < n) {
if (p[idx] - h[idx] < p[i] - h[i]) {
idx = i;
}
}
else {
idx = i;
}
}
if (idx == 1e9) break;
int mi = p[idx];
for (int i = 0; i < n; ++i) if (p[i] >= mi) {
if (p[i] - 1 < h[i]) {
return -1;
}
p[i] -= 1;
}
++cnt;
}
return cnt;
}
int solve() {
vector<int> ord(n);
iota(ALL(ord),0);
sort(ALL(ord), [&](int i, int j) {
return p[i] < p[j];
});
bool ok = true;
for (int i = 0; i+1 < n; ++i) {
int x = ord[i];
int y = ord[i+1];
if (p[x] == p[y]) {
if (h[x] != h[y]) {
ok = false;
break;
}
}
else {
if (h[x] > h[y]) {
ok = false;
break;
}
}
}
if (ok) {
for (int i = 0; i < n; ++i) if (p[i] < h[i]) {
ok = false;
break;
}
}
int ans = -1;
if (ok) {
ans = p[ord.back()] - h[ord.back()];
}
return ans;
}
int main() {
int t;
cin >> t;
while (t--) {
input();
cout << solve() << '\n';
}
// while (true) {
// gen();
// auto ch = h, cp = p;
// int x = solve();
// int y = naive();
// dbg(x)
// if (x != y) {
// for (int i = 0; i < n; ++i) {
// cerr << ch[i] << " \n"[i==n-1];
// }
// for (int i = 0; i < n; ++i) {
// cerr << cp[i] << " \n"[i==n-1];
// }
// dbg(x)
// dbg(y)
// break;
// }
// }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
4 4 3 2 4 2 5 3 6 2 1 10 100000 5 1 2 3 4 5 1 2 3 4 5 3 1 4 6 4 1 8
output:
2 99990 0 -1
result:
ok 4 number(s): "2 99990 0 -1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
10 1 1 2 2 2 7 2 7 1 6 8 1 1 1 1 3 8 2 4 4 9 7 4 5 5 5 5 8 6 6 6 2 3 3 10 3 2 6 1 8 2 4 4 6 8 9 4 7 9 10
output:
1 0 2 0 5 5 3 7 2 1
result:
ok 10 numbers
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3656kb
input:
100 1 4 9 2 57 42 67 52 2 9 53 13 68 1 5 10 1 11 41 1 4 8 1 7 16 5 1 12 66 2 14 33 21 83 11 29 1 20 22 2 29 67 59 98 4 1 12 85 1 26 16 98 5 1 4 47 5 8 8 37 40 58 11 31 54 66 89 2 22 12 75 63 1 10 10 1 34 37 7 7 16 21 62 3 16 1 9 46 55 96 4 44 2 1 4 24 4 2 1 23 18 29 28 82 68 4 73 77 66 6 80 84 72 8 ...
output:
5 10 15 5 30 4 9 -1 2 31 -1 43 31 53 0 3 34 20 59 7 43 28 50 33 14 51 13 47 3 90 23 19 0 35 13 17 51 5 84 43 16 85 6 32 28 15 24 3 36 -1 45 4 13 9 10 22 -1 33 13 25 9 42 30 17 45 26 68 32 8 1 6 13 23 18 68 3 -1 59 20 20 3 55 35 4 -1 92 10 7 18 59 11 51 55 3 85 42 14 39 28 2
result:
wrong answer 13th numbers differ - expected: '-1', found: '31'