QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#296909#6108. Permutation ArrangementPhantomThreshold#WA 0ms3800kbC++20926b2024-01-03 19:35:122024-01-03 19:35:12

Judging History

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

  • [2024-01-03 19:35:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3800kb
  • [2024-01-03 19:35:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	vector<int> a(n+5),vis(n+5);
	set<int> s;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]>0)vis[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(not vis[i])
			s.insert(i);
	}
	int cnt=0;
	function<void(int)> dfs=[&](int dep)
	{
		if(dep==n+1)
		{
			for(int i=1;i<=n;i++)
				cout<<a[i]<<" \n"[i==n];
			exit(0);
		}
		cnt++;
		if(cnt>=3000000)
		{
			cout<<-1<<endl;
			exit(0);
		}
		if(a[dep]!=-1)dfs(dep+1);
		int now=0;
		auto it=s.upper_bound(now);
		while(it!=s.end())
		{
			now=*it;
			if((dep==1 or abs(now-a[dep-1])!=1) and (dep==n or a[dep+1]==-1 or abs(now-a[dep+1])!=1))
			{
				a[dep]=now;
				s.erase(now);
				dfs(dep+1);
				s.insert(now);
				a[dep]=-1;
			}
			it=s.upper_bound(now);
		}
	};
	dfs(1);
	cout<<-1<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3728kb

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

input:

2
-1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3800kb

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

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

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

input:

10
4 -1 8 -1 -1 3 -1 9 -1 6

output:

-1

result:

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