QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624597#6108. Permutation Arrangementlmy11WA 0ms3832kbC++231.6kb2024-10-09 16:12:492024-10-09 16:12:49

Judging History

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

  • [2024-10-09 16:12:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-10-09 16:12:49]
  • 提交

answer

#include<bits/stdc++.h>
const int N=2e5+5;
using namespace std;
int read()
{
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			f=-f;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(int x)
{
	if(x<0)
	{
		x=-x;
		putchar('-');
	}
	if(x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}
string reads()
{
	string s;
	char ch=getchar();
	while(ch==' '||ch=='\n')
	{
		ch=getchar();
	}
	while(ch!=' '&&ch!='\n')
	{
		s+=ch;
		ch=getchar();
	}
	return s;
}
void writes(string s)
{
	for(int i=0;i<(int)s.length();i++)
	{
		putchar(s[i]);
	}
}
priority_queue< int,vector<int>,greater<int> >q;
bool f[N];
int s[N];
int ans[N];
int n;
void dfs(int x)
{
	if(x==n+1)
	{
		for(int i=1;i<=n;i++)
		{
			write(ans[i]);
			putchar(' ');
		}
		puts("");
		exit(0);
	}
	if(ans[x]!=-1) dfs(x+1);
	int a[6];
	for(int i=1;i<=min((int)q.size(),5);i++)
	{
		for(int j=1;j<=i;j++)
		{
			a[j]=q.top();
			q.pop();
		}
		for(int j=1;j<i;j++) q.push(a[j]);
		if(abs(ans[x-1]-a[i])>1 && abs(ans[x+1]-a[i])>1)
		{
			ans[x]=a[i];
			dfs(x+1);
		}
		q.push(a[i]);
		ans[x]=-1;
	}
//	if(q.size()>=5)
//	{
//		write(-1);
//		puts("");
//		exit (0);
//	}
}
int main()
{
	n=read();
	ans[0]=-1;
	ans[n+1]=-1;
	for(int i=1;i<=n;i++)
	{
		s[i]=read();
		if(s[i]!=-1) f[s[i]]=1;
		ans[i]=s[i];
	}
	for(int i=1;i<=n;i++)
		if(!f[i])
			q.push(i);
//	cout<<q.size()<<endl;
	dfs(1);
	write(-1);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

2
-1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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

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

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

input:

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

output:

-1

result:

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