QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123430#6108. Permutation ArrangementHEXU123WA 1ms3712kbC++141.6kb2023-07-12 16:17:552023-07-12 16:17:56

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:17:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3712kb
  • [2023-07-12 16:17:55]
  • 提交

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() < 10) 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; tmp.erase(x); break;
			}
		}
	}
	
	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;
}

詳細信息

Test #1:

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

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

input:

2
-1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

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

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

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: 0ms
memory: 3708kb

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

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

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

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: -100
Wrong Answer
time: 1ms
memory: 3712kb

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:

4 1 5 7 9 6 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:

wrong answer 1st numbers differ - expected: '1', found: '4'