QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#883595	#9785. Shrooks	DaiRuiChen007	WA	16ms	3840kb	C++17	1.2kb	2025-02-05 17:09:29	2025-02-05 17:09:29

Judging History

This is the latest submission verdict.

[2025-02-05 17:09:29]
Judged

Verdict: WA
Time: 16ms
Memory: 3840kb

Show

[2025-02-05 17:09:29]
Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,MOD=998244353;
int n,k,a[MAXN],b[MAXN];
void rot() {
	for(int i=1;i<=n;++i) b[i]=a[i],a[i]=-1;
	for(int i=1;i<=n;++i) if(~b[i]) a[n-b[i]+1]=i;
}
bool is(int x,int y) { return a[x]==-1||a[x]==y; }
void solve() {
	scanf("%d",&n),k=n/2;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	if(n&1) {
		int ans=0,f[4]={0,0,0,0};
		for(int o:{0,1,2,3}) {
			f[o]=is(n,k+1);
			for(int i=1;i<=k;++i) {
				f[o]=f[o]*((is(i,k+1-i)&&is(n-i,k+1+i))+(is(i,k+1-i)&&is(n-i,k+1+i)))%MOD;
			}
			ans=(ans+f[o])%MOD,rot();
		}
		for(int o:{0,1,2,3}) if(f[o]&&f[(o+1)%4]) --ans;
		printf("%d\n",(ans+MOD)%MOD);
	} else {
		int ans=0,f[5]={0,0,0,0,0};
		for(int o:{0,1,2,3}) {
			f[o]=is(k,n)&&is(n,k);
			for(int i=1;i<k;++i) {
				f[o]=f[o]*((is(i,k-i)&&is(n-i,k+i))+(is(i,k+i)&&is(n-i,k-i)))%MOD;
			}
			ans=(ans+f[o])%MOD,rot();
		}
		f[4]=1;
		for(int i=1;i<=k;++i) {
			f[4]=f[4]*((is(i,k+1-i)&&is(n+1-i,k+i))+(is(i,k+i)&&is(n+1-i,k+1-i)))%MOD;
		}
		ans=(ans+f[4])%MOD; if(f[0]&&f[2]) ans-=2; if(f[1]&&f[3]) ans-=2;
		printf("%d\n",(ans+MOD)%MOD);
	}
}
signed main() {
	int _; scanf("%d",&_);
	while(_--) solve();
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3712kb

input:

6
2
1 2
3
-1 -1 -1
4
1 -1 -1 -1
5
1 -1 -1 -1 5
6
3 -1 -1 -1 -1 4
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

6
2
1 2
3
-1 -1 -1
4
1 -1 -1 -1
5
1 -1 -1 -1 5
6
3 -1 -1 -1 -1 4
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

result:

ok 6 numbers

Test #3:

score: -100

Wrong Answer

time: 16ms

memory: 3840kb

input:

26874
7
-1 -1 7 1 5 3 -1
7
-1 -1 5 3 6 -1 7
7
-1 7 -1 2 3 6 -1
7
-1 2 7 1 5 3 -1
7
3 -1 2 6 1 4 -1
7
4 -1 5 6 1 -1 3
7
-1 -1 4 -1 7 2 -1
7
-1 6 -1 5 4 3 -1
7
6 7 1 2 5 4 -1
7
-1 5 -1 4 2 3 6
7
-1 4 3 5 7 6 -1
7
6 -1 -1 -1 7 5 -1
7
-1 -1 2 -1 4 -1 3
7
-1 -1 2 -1 6 -1 4
7
-1 5 6 2 7 4 -1
7
-1 -1 6 -1 ...

output:

result:

wrong answer 19th numbers differ - expected: '1', found: '0'