QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#803276 | #9832. If I Could Turn Back Time | ucup-team3723# | TL | 112ms | 3704kb | C++20 | 2.9kb | 2024-12-07 16:42:01 | 2024-12-07 16:42:06 |
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 = 20;
h.resize(n);
p.resize(n);
for (int i = 0; i < n; ++i) h[i] = rnd() % 100 + 1;
// sort(ALL(h));
vector<int> d(n);
for (int i = 0; i < n; ++i) d[i] = rnd() % 10;
sort(ALL(d));
for (int i = 0; i < n; ++i) p[i] = h[i] + d[i];
}
int naive() {
int cnt = 0;
for (int i = 0; i < n; ++i) if (p[i] < h[i]) return -1;
while (true) {
int macnt=-1, mi;
for (int i = 0; i < n; ++i) if (p[i] > h[i]) {
if (p[i] - h[i] > macnt) {
macnt = p[i] - h[i];
mi = p[i];
}
else if (p[i] - h[i] == macnt) {
mi = min(mi, p[i]);
}
}
if (macnt > 0) {
for (int i = 0; i < n; ++i) if (p[i] >= mi) {
p[i] -= 1;
}
++cnt;
}
else {
break;
}
}
// for (int i = 0; i < n; ++i) cerr << p[i] << " \n"[i==n-1];
for (int i = 0; i < n; ++i) if (p[i] != h[i]) {
return -1;
}
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];
int dx = p[x]-h[x];
int dy = p[y]-h[y];
if (dx < 0 || dy < 0) {
ok = false;
break;
}
if (p[x] == p[y]) {
if (h[x] != h[y]) {
ok = false;
break;
}
}
else {
assert(p[x] < p[y]);
if (h[x] > h[y] || dx > dy) {
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 << naive() << '\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;
// }
// }
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3588kb
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: 3628kb
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: 0
Accepted
time: 1ms
memory: 3640kb
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 -1 53 0 3 34 20 59 7 -1 -1 50 33 14 51 -1 47 3 90 23 19 0 35 13 17 51 -1 84 -1 16 85 6 32 28 -1 24 3 36 -1 45 -1 13 9 10 22 -1 33 13 -1 9 42 -1 17 45 26 68 32 8 -1 6 13 23 18 68 3 -1 59 -1 20 3 55 -1 4 -1 92 10 7 18 59 11 51 55 3 -1 42 14 39 28 -1
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 3704kb
input:
1000 1 295 730 1 562 588 1 440 834 2 170 150 739 630 1 308 536 1 11 432 2 302 1 345 47 1 26 48 2 79 433 85 927 1 194 563 1 95 289 1 129 481 1 2 76 2 942 297 984 343 1 26 309 3 342 236 182 898 833 706 3 949 1 1 990 142 142 1 350 377 1 489 554 2 603 617 750 999 2 86 60 454 308 1 349 873 2 3 124 11 258...
output:
435 26 394 569 228 421 -1 22 494 369 194 352 74 -1 283 -1 -1 27 65 382 368 524 134 136 399 20 -1 317 76 -1 11 117 248 -1 747 234 39 257 -1 243 161 28 410 -1 219 402 517 0 -1 383 -1 -1 560 -1 150 283 69 -1 5 679 736 -1 178 241 6 154 250 7 152 521 -1 510 -1 253 689 152 163 455 7 -1 -1 -1 -1 127 58 138...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
10000 3 1 2 3 1 2 3 3 4 2 3 2 4 3 4 1 2 2 1 1 2 2 3 4 2 3 2 3 2 2 1 1 4 1 2 3 2 2 3 3 2 3 1 1 1 4 2 1 4 3 2 1 1 2 3 3 1 4 3 1 3 3 1 3 3 2 3 4 4 1 2 3 1 4 1 2 2 3 1 2 2 2 4 3 2 3 2 2 3 1 2 3 2 1 1 3 3 1 4 2 1 1 2 1 1 1 1 4 1 3 1 3 2 1 2 2 3 1 4 2 3 1 4 3 1 2 2 1 1 1 3 4 4 4 1 3 4 4 3 3 1 3 1 3 1 1 3 ...
output:
0 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 8ms
memory: 3644kb
input:
10000 4 3 1 3 3 3 1 3 3 3 3 1 2 3 1 3 4 1 1 2 3 2 3 3 3 4 1 1 2 1 3 1 2 2 4 1 3 2 2 3 3 3 2 4 1 1 3 2 3 1 4 2 4 1 3 2 1 3 4 2 2 3 2 2 1 3 4 4 4 1 3 3 1 2 3 4 4 4 2 2 2 4 2 2 3 4 4 1 3 3 2 1 4 4 3 4 1 2 1 3 2 3 4 3 4 1 2 2 2 3 2 2 3 4 2 3 4 3 3 3 4 4 4 1 2 4 2 3 3 4 2 3 3 1 1 4 2 4 2 2 1 3 3 4 2 4 1 ...
output:
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 0 -1 -1 -1 -1 -1 -1 -1 2 2 -1 -1 -1 -1 -1 1 -1 -1 -1 3 -1 -1 2 -1 1 -1 -1 -1 -1 1 3 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 0 -1 -1 -1 -1 1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 ...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 112ms
memory: 3636kb
input:
10000 1 1992 3361 1 2344 6367 3 2384 2669 2391 2552 9612 9008 8 2772 68 2961 3038 1455 1952 1700 1475 7154 2454 7344 7520 4697 6299 5998 4718 3 1 2377 3674 1563 6671 4111 1 835 3970 2 90 3808 905 3966 1 1884 4228 1 2230 4764 1 2666 4380 1 5235 6086 2 9014 2301 9258 2840 1 4146 9155 3 4232 131 1 6134...
output:
1369 4023 6943 4482 -1 3135 -1 2344 2534 1714 851 -1 5009 -1 2377 1 -1 2771 641 197 -1 -1 523 3784 -1 2141 16 -1 -1 -1 -1 4539 2127 931 -1 -1 7687 2636 161 1413 -1 -1 5838 3943 115 4410 4363 -1 1396 1195 1971 992 -1 1275 4611 6264 442 -1 2103 -1 4570 5051 4386 1800 5903 468 -1 -1 1384 1035 5042 2423...
result:
ok 10000 numbers
Test #8:
score: -100
Time Limit Exceeded
input:
10000 7 38298 219279 150117 108638 38514 262931 190184 49359 632891 212333 136390 49805 733473 275123 8 292669 243756 357925 275144 154345 270254 1924 152155 644616 329383 444406 539603 331796 500761 9253 171890 5 48205 121332 284583 6912 195063 483501 636162 920123 223333 768268 17 111673 400728 31...
output:
470542 -1 635540 -1 448149 -1 -1 29420 374065 -1 311800 31168 497379 -1 -1 122242 389855 684381 459586 148108 587025 -1 250271 -1 -1 -1 348760 297370 -1 336091 -1 -1 -1 102640 -1 -1 -1 292881 -1 -1 -1 472732 -1 549997 111066 -1 -1 25565 745743 444057 -1 -1 175829 610018 268482 16035 -1 447221 124317...