QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#108628	#5526. Jewel of Data Structure Problems	grass8cow	WA	36ms	3788kb	C++14	667b	2023-05-25 20:15:49	2023-05-25 20:15:52

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-25 20:15:52]
评测

测评结果：WA
用时：36ms
内存：3788kb

查看

[2023-05-25 20:15:49]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,q,p[201000],t,z;
void fk(int i,int f){
	t+=f*((i&1)!=(p[i]&1));
	if(i>1)z+=f*(p[i-1]<p[i]);
	if(i<n)z+=f*(p[i]<p[i+1]);
}
bool vi[201000];
int o;
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	o=(n&1);
	for(int i=1;i<=n;i++)if(!vi[i]){
		o^=1;int u=i;
		while(!vi[u])vi[u]=1,u=p[u];
	}
	for(int i=1;i<=n;i++)fk(i,1);
	for(int i=1,u,v;i<=q;i++){
		scanf("%d%d",&u,&v);o^=1;
		fk(u,-1),fk(v,-1);swap(p[u],p[v]);fk(u,1),fk(v,1);
		if(o)printf("%d\n",n);
		else if(z==2*(n-1))puts("-1");
		else if(t)printf("%d\n",n-1);
		else printf("%d\n",n-2);
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3644kb

input:

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 36ms

memory: 3624kb

input:

output:

2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
...

result:

ok 200000 numbers

Test #3:

score: -100

Wrong Answer

time: 29ms

memory: 3788kb

input:

output:

result:

wrong answer 3rd numbers differ - expected: '2', found: '-1'