QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123443#6108. Permutation ArrangementHEXU123TL 842ms15176kbC++141.6kb2023-07-12 16:32:512023-07-12 16:32:53

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 16:32:53]
  • 评测
  • 测评结果:TL
  • 用时:842ms
  • 内存:15176kb
  • [2023-07-12 16:32:51]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N = 1e6 + 5;

int n;
vector <int> a, b, c, vis, used;
clock_t start;

void init () {}

void DFS (int u, int lim) {
	if (u >= lim) {
		
		for (int i = 1; i <= n; ++i) {
			cout << a[i] << " \n"[i == n];
		}
		exit (0);
		/*cout << clock () - start << "ms" << endl;
		exit (0);*/
	}
	for (int i = 0; i < lim; ++i) {
		if (used[i]) continue;
		if (abs (a[b[u] - 1] - c[i]) == 1) continue;
		else if (abs (a[b[u] + 1] - c[i]) == 1) continue;
		else {
			a[b[u]] = c[i], used[i] = true;
			DFS (u + 1, lim);
			a[b[u]] = -1, used[i] = false;
		}
	}
}

set<int> tmp;
void charming () {
	init ();
	cin >> n;
	a = vis = used = vector <int> (n + 5);
	
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
	}
	
	for (int i = 1; i <= n; ++ i) tmp.insert(i);
	for (int i = 1; i <= n; ++ i) if (a[i] != -1) tmp.erase(a[i]);
	
	for (int i = 1; i <= n; ++ i) {
		if (tmp.size() < 70000) break;
		if (a[i] != -1) continue;
		for (auto x : tmp) {
			if (abs(a[i-1] - x) != 1 && abs(a[i+1] - x) != 1) {
				a[i] = x; break;
			}
		}
		tmp.erase(a[i]);
	}
	
	a[0] = a[n + 1] = -1; 
	for (int i = 1; i <= n; ++i) {
		//a[i] = -1
		if (a[i] > 0) vis[a[i]] = 1;
		else b.emplace_back (i);
	}
	
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) c.emplace_back (i);
	}
	
	
	
	DFS (0, (int) b.size ());
	cout << -1 << endl;
}

signed main () {
	ios_base::sync_with_stdio (false);
	cin.tie (NULL);
	cout.tie (NULL);
	start = clock ();
	charming ();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3468kb

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: 1ms
memory: 3464kb

input:

2
-1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3464kb

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: 1ms
memory: 3632kb

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: 1ms
memory: 3636kb

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: 1ms
memory: 3460kb

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: 3656kb

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: 3568kb

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: 3676kb

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: 3616kb

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: 3640kb

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: 167ms
memory: 12152kb

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: 326ms
memory: 13244kb

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: 546ms
memory: 14256kb

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: 0
Accepted
time: 810ms
memory: 15056kb

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...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 842ms
memory: 15056kb

input:

100000
-1 27966 81904 9017 55897 -1 22386 28339 78033 75545 -1 -1 -1 -1 -1 -1 -1 -1 40290 -1 -1 4085 -1 -1 -1 54033 -1 83085 7293 33403 63978 57251 23205 21269 -1 69158 91817 32392 -1 40930 29249 -1 -1 90547 -1 61890 2757 -1 -1 25951 2 11955 -1 32843 -1 -1 -1 -1 -1 72553 -1 -1 12153 3456 8766 1337 5...

output:

3 27966 81904 9017 55897 4 22386 28339 78033 75545 5 7 9 6 8 10 16 11 40290 19 21 4085 20 22 28 54033 30 83085 7293 33403 63978 57251 23205 21269 31 69158 91817 32392 33 40930 29249 34 37 90547 39 61890 2757 41 43 25951 2 11955 42 32843 44 46 48 45 51 72553 54 56 12153 3456 8766 1337 56753 59811 782...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 809ms
memory: 15116kb

input:

100000
68642 42161 58555 -1 -1 56399 -1 -1 -1 46805 -1 99806 -1 -1 50564 89557 -1 71730 10222 -1 57943 22247 20883 41318 -1 87264 87299 81755 30525 -1 17832 80092 96961 13885 -1 -1 -1 -1 81144 24604 41393 -1 7946 55607 21917 -1 -1 -1 88484 -1 28189 -1 17016 -1 80797 -1 69375 73602 -1 -1 66135 -1 541...

output:

68642 42161 58555 1 3 56399 5 8 6 46805 17 99806 19 33 50564 89557 34 71730 10222 35 57943 22247 20883 41318 36 87264 87299 81755 30525 38 17832 80092 96961 13885 40 47 52 54 81144 24604 41393 57 7946 55607 21917 61 66 62 88484 67 28189 69 17016 70 80797 71 69375 73602 72 77 66135 73 54183 82 84 244...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 820ms
memory: 15140kb

input:

100000
21150 -1 -1 63979 -1 26074 -1 -1 18027 7589 -1 -1 -1 -1 -1 76834 -1 -1 -1 -1 43596 -1 69422 -1 -1 -1 -1 58471 -1 -1 20704 64235 -1 -1 18411 35496 10521 -1 19869 73858 33268 -1 -1 67948 -1 95775 2656 -1 63959 1272 -1 31873 83923 1506 -1 35987 19931 -1 91682 -1 38769 41599 38858 -1 9184 88362 4...

output:

21150 3 5 63979 7 26074 8 10 18027 7589 11 18 12 19 23 76834 26 30 27 33 43596 34 69422 35 37 39 36 58471 38 42 20704 64235 44 49 18411 35496 10521 50 19869 73858 33268 51 58 67948 52 95775 2656 63 63959 1272 64 31873 83923 1506 65 35987 19931 66 91682 68 38769 41599 38858 69 9184 88362 49858 71 73 ...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 805ms
memory: 15176kb

input:

100000
-1 91842 -1 -1 -1 -1 90929 23192 71997 16066 221 -1 -1 -1 -1 -1 3072 -1 -1 -1 -1 -1 -1 1186 70844 -1 37187 -1 22908 57578 30341 36529 -1 -1 -1 51436 -1 -1 23780 -1 84615 -1 23459 -1 -1 -1 65197 -1 -1 99344 -1 -1 78774 88007 -1 -1 -1 -1 78291 47153 7633 -1 14431 -1 -1 -1 53029 -1 95615 73415 2...

output:

2 91842 4 6 10 13 90929 23192 71997 16066 221 17 19 21 25 22 3072 26 29 27 30 33 36 1186 70844 34 37187 37 22908 57578 30341 36529 42 45 43 51436 46 48 23780 50 84615 51 23459 54 59 55 65197 60 62 99344 64 67 78774 88007 65 72 74 76 78291 47153 7633 73 14431 81 84 82 53029 86 95615 73415 20673 88 90...

result:

ok 100000 numbers

Test #20:

score: -100
Time Limit Exceeded

input:

100000
79679 -1 -1 40321 37599 -1 48462 43851 -1 62731 95129 28592 58526 -1 -1 -1 -1 99421 95174 11621 -1 66767 46564 96130 95435 82401 79166 -1 59852 -1 4774 71513 38650 44108 -1 -1 -1 79454 -1 -1 -1 71955 -1 92239 68129 51421 -1 73095 -1 81006 44505 -1 60808 88994 14959 -1 13978 31639 -1 -1 76479 ...

output:


result: