QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722821 | #1873. Array | Made_in_Code | AC ✓ | 165ms | 5200kb | C++14 | 1.2kb | 2024-11-07 20:15:57 | 2024-11-07 20:15:57 |
Judging History
answer
#include <iostream>
using namespace std;
const int kMaxN = 2e5 + 1;
int t, n, m, k, a[kMaxN], b[kMaxN];
void Solve() {
cin >> n, m = n, k = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i], b[i] = 0;
}
for (int i = 1; i <= n; i++) {
if (a[i] <= n) {
m = min(m, a[i] - i + 1);
}
if (a[i] < i || a[i] < a[i - 1]) {
cout << -1 << '\n';
return;
}
}
if (a[1] == n + 1) {
cout << -1 << '\n';
return;
}
for (int i = 1; i < m; i++) {
b[i] = i;
}
b[a[1]] = m;
for (int i = 1; i < n; i++) {
for (; k <= n && b[k]; k++) {
}
if (!b[i]) {
cout << -1 << '\n';
return;
} else if (a[i] == a[i + 1]) {
b[k] = b[i];
} else if (a[i + 1] <= n) {
b[a[i + 1]] = b[i];
} else if (i + 1 == k) {
cout << -1 << '\n';
return;
} else {
break;
}
}
for (; k <= n; k++) {
!b[k] && (b[k] = b[k - 1]);
}
for (int i = 1; i <= n; i++) {
cout << b[i] << " \n"[i == n];
}
}
int main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
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: 3624kb
input:
3 4 3 3 5 5 7 4 6 6 7 8 8 8 5 2 3 4 4 6
output:
1 1 2 2 1 2 3 4 2 1 3 -1
result:
ok 233
Test #2:
score: 0
Accepted
time: 125ms
memory: 5200kb
input:
23198 7 1 2 3 4 5 6 7 7 1 2 3 4 5 6 8 7 1 2 3 4 5 7 7 7 1 2 3 4 5 7 8 7 1 2 3 4 5 8 8 7 1 2 3 4 6 6 7 7 1 2 3 4 6 6 8 7 1 2 3 4 6 7 7 7 1 2 3 4 6 7 8 7 1 2 3 4 6 8 8 7 1 2 3 4 7 7 7 7 1 2 3 4 7 7 8 7 1 2 3 4 7 8 8 7 1 2 3 4 8 8 8 7 1 2 3 5 5 6 7 7 1 2 3 5 5 6 8 7 1 2 3 5 5 7 7 7 1 2 3 5 5 7 8 7 1 2 ...
output:
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 -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 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 233
Test #3:
score: 0
Accepted
time: 104ms
memory: 3652kb
input:
2000 1000 964 987 987 989 992 999 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1001 1...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 233
Test #4:
score: 0
Accepted
time: 107ms
memory: 4504kb
input:
16 100000 44700 98571 99279 99995 99998 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 100001 1...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 233
Test #5:
score: 0
Accepted
time: 106ms
memory: 4504kb
input:
1006 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
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 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 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 233
Test #6:
score: 0
Accepted
time: 165ms
memory: 4380kb
input:
106 20000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
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 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 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 233
Test #7:
score: 0
Accepted
time: 139ms
memory: 5144kb
input:
58796 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 11 10 1 2 3 4 5 6 7 8 10 10 10 1 2 3 4 5 6 7 8 10 11 10 1 2 3 4 5 6 7 8 11 11 10 1 2 3 4 5 6 7 9 9 10 10 1 2 3 4 5 6 7 9 9 11 10 1 2 3 4 5 6 7 9 10 10 10 1 2 3 4 5 6 7 9 10 11 10 1 2 3 4 5 6 7 9 11 11 10 1 2 3 4 5 6 7 10 10 10 10 1 2 3 4 5 6 7 10 10...
output:
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 -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 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 233