QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #774817 | #6108. Permutation Arrangement | rlc202204 | TL | 881ms | 6832kb | C++17 | 947b | 2024-11-23 13:55:20 | 2024-11-23 13:55:25 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int n;
int a[N] = {0};
int pos[N] = {0}, cur = 0;
bool flg = false;
bool vis[N] = {false};
void dfs(int k) {
if (flg)
return;
if (k > cur) {
flg = true;
return;
}
for (int i = 1; i <= n; i++)
if (!vis[i] && ((pos[k] == 1 || abs(i - a[pos[k] - 1]) != 1) && (pos[k] == n || a[pos[k] + 1] == -1 || abs(i - a[pos[k] + 1]) != 1))) {
a[pos[k]] = i;
vis[i] = true;
dfs(k + 1);
if (flg)
return;
vis[i] = false;
a[pos[k]] = -1;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] != -1)
vis[a[i]] = true;
if (a[i] == -1)
pos[++cur] = i;
}
dfs(1);
if (flg) {
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
}
else {
cout << -1 << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
10 3 -1 10 -1 8 -1 -1 -1 -1 -1
output:
3 1 10 2 8 4 6 9 5 7
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
2 -1 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
10 -1 -1 -1 8 -1 2 10 -1 -1 3
output:
1 4 6 8 5 2 10 7 9 3
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
10 -1 2 -1 6 -1 1 -1 5 -1 3
output:
4 2 8 6 9 1 7 5 10 3
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 -1 3 -1 -1 5 -1 9 -1 -1 -1
output:
1 3 6 2 5 7 9 4 8 10
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
10 4 -1 8 -1 -1 3 -1 9 -1 6
output:
4 1 8 5 10 3 7 9 2 6
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
1000 80 360 454 409 303 639 154 486 365 955 -1 -1 625 488 726 -1 94 348 57 -1 287 472 551 981 106 381 199 877 660 736 762 207 -1 59 437 -1 -1 343 593 -1 151 225 -1 -1 430 854 771 378 785 -1 668 617 404 272 -1 871 305 920 507 101 -1 376 123 959 293 327 286 416 77 677 388 336 53 833 932 633 855 744 25...
output:
80 360 454 409 303 639 154 486 365 955 5 21 625 488 726 27 94 348 57 45 287 472 551 981 106 381 199 877 660 736 762 207 55 59 437 64 66 343 593 70 151 225 71 79 430 854 771 378 785 87 668 617 404 272 97 871 305 920 507 101 103 376 123 959 293 327 286 416 77 677 388 336 53 833 932 633 855 744 257 112...
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
1000 678 -1 739 723 -1 -1 226 881 -1 923 -1 80 568 648 16 480 114 400 -1 527 221 171 931 783 937 959 192 552 363 -1 -1 874 734 940 393 -1 733 915 327 117 -1 190 637 -1 -1 -1 808 300 350 658 720 437 525 -1 -1 876 699 428 493 314 883 139 833 22 252 274 -1 83 -1 376 950 -1 732 476 706 561 837 174 318 7...
output:
678 3 739 723 5 7 226 881 12 923 13 80 568 648 16 480 114 400 19 527 221 171 931 783 937 959 192 552 363 21 23 874 734 940 393 25 733 915 327 117 28 190 637 32 34 36 808 300 350 658 720 437 525 35 48 876 699 428 493 314 883 139 833 22 252 274 51 83 60 376 950 64 732 476 706 561 837 174 318 772 70 74...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
1000 -1 585 392 262 972 807 128 -1 558 -1 -1 678 600 472 -1 -1 -1 233 958 -1 -1 651 -1 622 739 -1 151 -1 93 935 -1 55 120 200 755 -1 674 -1 -1 1 -1 -1 -1 -1 -1 446 -1 -1 -1 605 -1 263 -1 43 491 -1 -1 -1 -1 982 -1 388 556 -1 589 -1 -1 448 -1 -1 -1 607 -1 -1 -1 -1 -1 -1 750 40 -1 -1 555 872 -1 -1 -1 5...
output:
2 585 392 262 972 807 128 3 558 6 9 678 600 472 10 12 15 233 958 13 16 651 17 622 739 19 151 20 93 935 21 55 120 200 755 22 674 24 26 1 25 28 30 32 29 446 31 34 37 605 35 263 41 43 491 44 48 50 58 982 49 388 556 51 589 59 62 448 66 71 74 607 75 78 76 79 83 85 750 40 84 88 555 872 89 92 90 535 94 97 ...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
1000 202 -1 -1 -1 -1 377 -1 -1 -1 -1 205 -1 -1 -1 470 -1 -1 -1 -1 151 869 678 72 -1 834 -1 -1 37 626 670 -1 902 178 -1 -1 389 500 732 -1 -1 676 109 533 -1 -1 812 731 618 -1 -1 4 108 513 948 312 -1 388 -1 629 -1 190 316 544 237 53 -1 -1 -1 -1 -1 358 226 -1 -1 783 -1 -1 875 634 772 212 56 -1 839 808 2...
output:
202 1 3 5 8 377 6 9 11 14 205 15 20 16 470 21 23 26 22 151 869 678 72 24 834 27 29 37 626 670 28 902 178 31 34 389 500 732 32 36 676 109 533 38 40 812 731 618 39 41 4 108 513 948 312 42 388 43 629 46 190 316 544 237 53 47 52 54 57 55 358 226 58 62 783 63 68 875 634 772 212 56 69 839 808 254 70 73 37...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
1000 -1 -1 -1 -1 -1 -1 -1 209 570 -1 552 -1 -1 -1 611 908 536 -1 663 -1 -1 487 -1 -1 -1 -1 -1 -1 365 -1 -1 -1 -1 918 24 -1 -1 -1 973 -1 -1 286 474 -1 585 349 -1 -1 605 735 367 -1 -1 -1 -1 -1 -1 -1 -1 -1 473 -1 489 -1 -1 662 283 -1 -1 -1 -1 -1 -1 -1 -1 -1 260 -1 987 -1 -1 -1 -1 -1 -1 681 -1 -1 -1 -1 ...
output:
1 4 6 9 5 7 10 209 570 11 552 12 15 17 611 908 536 16 663 18 21 487 19 22 25 23 26 28 365 27 30 32 34 918 24 33 35 37 973 38 40 286 474 39 585 349 41 43 605 735 367 44 46 48 45 47 49 51 53 55 473 54 489 56 58 662 283 57 61 63 69 62 64 70 72 76 260 71 987 73 77 79 81 83 80 681 85 87 89 86 794 460 88 ...
result:
ok 1000 numbers
Test #12:
score: 0
Accepted
time: 479ms
memory: 5552kb
input:
100000 80156 53723 42435 94255 41204 62135 89137 63931 20313 82118 83746 -1 9784 47210 40385 56772 47115 62130 41799 -1 84401 60635 51717 44994 62106 30835 -1 3666 75796 99260 12541 22017 5889 50591 39341 64594 82252 28787 63703 17015 82949 -1 73096 81195 75623 49081 93248 32712 12890 8543 73532 -1 ...
output:
80156 53723 42435 94255 41204 62135 89137 63931 20313 82118 83746 4 9784 47210 40385 56772 47115 62130 41799 7 84401 60635 51717 44994 62106 30835 12 3666 75796 99260 12541 22017 5889 50591 39341 64594 82252 28787 63703 17015 82949 18 73096 81195 75623 49081 93248 32712 12890 8543 73532 24 36 58486 ...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 699ms
memory: 6088kb
input:
100000 39130 -1 11138 84004 29682 84022 26702 68949 34582 45358 37675 5976 12002 -1 23453 26519 17100 82306 -1 47671 77312 24741 -1 87776 35007 -1 97897 10993 32298 63548 -1 57212 -1 64139 -1 35117 32732 83918 24358 48335 43824 60441 77020 1597 7404 -1 93716 43227 24087 -1 -1 64744 83051 29762 67839...
output:
39130 1 11138 84004 29682 84022 26702 68949 34582 45358 37675 5976 12002 7 23453 26519 17100 82306 9 47671 77312 24741 12 87776 35007 13 97897 10993 32298 63548 15 57212 25 64139 27 35117 32732 83918 24358 48335 43824 60441 77020 1597 7404 29 93716 43227 24087 33 36 64744 83051 29762 67839 78964 603...
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 881ms
memory: 6832kb
input:
100000 66918 55074 25554 -1 66110 -1 8972 -1 -1 30932 14523 90341 2556 56158 75463 38730 68035 16608 -1 69056 -1 5052 66098 16105 -1 -1 -1 -1 53014 22541 -1 50316 33746 -1 -1 -1 13215 89809 -1 48636 92023 -1 56017 -1 65969 -1 -1 6416 -1 57469 -1 -1 29120 46136 68421 -1 93185 64883 -1 30896 92631 390...
output:
66918 55074 25554 5 66110 9 8972 10 12 30932 14523 90341 2556 56158 75463 38730 68035 16608 13 69056 16 5052 66098 16105 17 19 21 18 53014 22541 24 50316 33746 26 30 32 13215 89809 31 48636 92023 34 56017 38 65969 41 47 6416 42 57469 51 55 29120 46136 68421 52 93185 64883 56 30896 92631 39004 56714 ...
result:
ok 100000 numbers
Test #15:
score: -100
Time Limit Exceeded
input:
100000 99590 -1 -1 -1 87466 35 -1 -1 61223 -1 99170 -1 -1 537 -1 -1 -1 -1 -1 66657 52066 -1 42749 -1 78144 -1 9520 -1 77022 -1 9997 8588 -1 -1 -1 68476 -1 -1 -1 -1 85365 -1 -1 23509 -1 -1 83937 6253 -1 -1 -1 65429 15170 -1 -1 -1 30500 38057 -1 -1 -1 91924 65445 23389 39518 -1 61488 70586 16274 21358...
output:
99590 3 5 8 87466 35 4 6 61223 10 99170 15 17 537 16 19 22 24 27 66657 52066 23 42749 30 78144 31 9520 32 77022 33 9997 8588 34 36 39 68476 40 46 48 51 85365 47 49 23509 52 55 83937 6253 53 59 62 65429 15170 63 66 64 30500 38057 77 80 82 91924 65445 23389 39518 83 61488 70586 16274 21358 75372 84 86...