QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395591#5529. Most Annoying Constructive ProblemXun_xiaoyaoWA 7ms3880kbC++142.9kb2024-04-21 16:28:322024-04-21 16:28:35

Judging History

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

  • [2024-04-21 16:28:35]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3880kb
  • [2024-04-21 16:28:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;
}
int p[1010],num[1010],cnt,tot;
bool vis[1010];
int lgx[1010],rgx[1010];
void calc(int n,int k)
{
	if(n<=5)
	{
		for(int i=1;i<=n;i++) p[i]=i;
		do
		{
			tot=0;
			for(int l=1;l<=n;l++)
			{
				for(int i=1;i<=n;i++) vis[i]=false;cnt=0;
				for(int r=l;r<=n;r++)
				{
					for(int i=p[r]+1;i<=n;i++) if(vis[i]) cnt++;
					if(cnt&1) tot++;
					vis[p[r]]=true;
				}
			}
			if(tot==k) return;
		}while(next_permutation(p+1,p+n+1));		
	}
	if(k==0)
	{
		for(int i=1;i<=n;i++) p[i]=i;
		return;
	}
	if(k<n-1)
	{
		for(int i=1;i<=n;i++) p[i];
		p[k]=k+2,p[k+1]=k,p[k+2]=k+1;
		return;
	}
	if(k==n*(n-1)/2-(n-1)/2)
	{
		for(int i=1;i<=n;i+=2) num[i]=i+3;
		for(int i=2;i<=n;i+=2) num[i]=i-1;
		sort(num+1,num+n+1);
		for(int i=1;i<=n;i+=2) p[i]=lower_bound(num+1,num+n+1,i+3)-num;
		for(int i=2;i<=n;i+=2) p[i]=lower_bound(num+1,num+n+1,i-1)-num;
		return;
	}
	if(k<=(n-2)*(n-3)/2-(n-3)/2+n-1)
	{
		p[n]=n-1,p[n-1]=n;
		calc(n-2,k-(n-1));
		return;
	}
	
	for(int i=2;i<n;i+=2) num[i]=i+2;
	for(int i=3;i<n;i+=2) num[i]=i-2;
	sort(num+2,num+n);
	for(int i=2;i<n;i+=2) p[i]=lower_bound(num+2,num+n,i+2)-num-1;
	for(int i=3;i<n;i+=2) p[i]=lower_bound(num+2,num+n,i-2)-num-1;

	for(int i=1;i<n;i++)
	{
		lgx[i]=rgx[i]=0;
		cnt=0;
		for(int j=2;j<=n;j++)
		{
			if(i>p[j]) cnt++;
			if((cnt+(j!=3))&2) lgx[i]++;
		}
		cnt=0;
		for(int j=n-1;j>1;j--)
		{
			if(i<=p[j]) cnt++;
			if((cnt+((n&1)||(j==n-3)))&2) rgx[i]++;
		}
	}

	k-=(n-2)*(n-3)/2-(n-3)/2;
	for(int l=1;l<n;l++)
	for(int r=1;r<n;r++)
	if(l<r)
	{
		if(k==lgx[l]+rgx[r]+((l-1+r-1)&1))
			{p[1]=l,p[n]=r+1;break;}
	}
	else if(l>r)
	{
		if(k==lgx[l]+rgx[r]+((l-1+r-1+1)&1))
			{p[1]=l+1,p[n]=r;break;}
	}
	else
	{
		if(k==lgx[l]+rgx[r]+((l-1+r-1)&1))
			{p[1]=l,p[n]=r+1;break;}
		if(k==lgx[l]+rgx[r]+((l-1+r-1+1)&1))
			{p[1]=l+1,p[n]=r;break;}
	}

	if(p[1]<p[n])
	{
		for(int i=2;i<n;i++) if(p[i]>=p[1]) p[i]++;
		for(int i=2;i<n;i++) if(p[i]>=p[n]) p[i]++;
	}
	else
	{
		for(int i=2;i<n;i++) if(p[i]>=p[n]) p[i]++;
		for(int i=2;i<n;i++) if(p[i]>=p[1]) p[i]++;
	}
}
int n,k;
void solve()
{
	n=Qread(),k=Qread();

	if(n<=5)
	{
		for(int i=1;i<=n;i++) p[i]=i;
		do
		{
			tot=0;
			for(int l=1;l<=n;l++)
			{
				for(int i=1;i<=n;i++) vis[i]=false;cnt=0;
				for(int r=l;r<=n;r++)
				{
					for(int i=p[r]+1;i<=n;i++) if(vis[i]) cnt++;
					if(cnt&1) tot++;
					vis[p[r]]=true;
				}
			}
			if(tot==k) break;
		}while(next_permutation(p+1,p+n+1));
		if(tot!=k) return printf("NO\n"),void();
	}
	else
	{
		if(k>n*(n-1)/2-(n-1)/2) return printf("NO\n"),void();
		calc(n,k);
	}
	printf("YES\n");
	for(int i=1;i<=n;i++) printf("%d ",p[i]);printf("\n");
}
int main()
{
	int T=Qread();
	while(T--) solve();
	return 0;
}

详细

Test #1:

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

input:

4
1 0
3 3
4 1
6 15

output:

YES
1 
YES
3 2 1 
YES
1 3 4 2 
NO

result:

ok Correct (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 3808kb

input:

5951
27 255
28 371
31 320
33 201
32 199
31 108
15 78
27 32
24 268
20 4
14 82
29 202
33 85
26 104
31 380
27 330
20 140
29 192
21 63
17 89
20 41
32 444
20 76
27 114
33 330
26 249
33 301
24 87
25 72
14 49
25 281
21 58
15 48
16 19
14 0
22 175
11 7
30 43
31 259
22 112
12 30
30 111
33 268
30 287
19 150
15...

output:

YES
21 3 1 5 2 8 4 10 6 12 9 14 11 16 13 18 15 19 17 20 7 23 22 25 24 27 26 
NO
YES
21 3 1 5 2 7 4 9 6 11 8 13 10 16 12 18 15 19 17 20 14 23 22 25 24 27 26 29 28 31 30 
YES
3 1 2 5 2 7 4 9 6 11 8 13 10 16 12 18 15 19 18 21 20 23 22 25 24 27 26 29 28 31 30 33 32 
YES
3 1 2 5 2 7 9 7 8 11 8 13 10 16 1...

result:

wrong answer wrong number of odd subarrays (test case 1)