QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#885102	#9785. Shrooks	piggy123	WA	30ms	5704kb	C++17	5.2kb	2025-02-06 13:45:02	2025-02-06 13:45:03

Judging History

This is the latest submission verdict.

[2025-02-06 13:45:03]
Judged

Verdict: WA
Time: 30ms
Memory: 5704kb

Show

[2025-02-06 13:45:02]
Submitted

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll a[200005],b[200005],fl[8],n,ans;
const ll mod=998244353;

void solve(ll* a,ll p=0) {
	ll k=n/2,fn=1;
	if ((a[1]==k+1||a[1]==-1)&&(a[n]==k||a[n]==-1)) {
		for (ll j=2; 2*j-1<=n; j++) {
			if (a[j]==-1&&a[n-j+1]==-1)fn*=2,fn%=mod;
			else {
				if (min(a[j],a[n-j+1])==-1) {
					if (max(a[j],a[n-j+1])==k+j||max(a[j],a[n-j+1])==k-j+1) {

					} else {
						fn=0;
					}
				} else {
					if ((max(a[j],a[n-j+1])==k+j&&min(a[j],a[n-j+1])==k-j+1)||(min(a[j],a[n-j+1])==k+j&&max(a[j],a[n-j+1])==k-j+1)) {

					} else {
						fn=0;
					}
				}
			}
		}
	} else {
		fn=0;
	}
	if (fn)fl[p]=1;
	ans+=fn;
	ans%=mod;
}
void solve2(ll* a,ll p) {
	ll k=n/2,fn=1;
	if ((a[1]==k||a[1]==-1)&&(a[k+1]==n||a[k+1]==-1)) {
		for (ll j=0; j<k-1; j++) {

			ll p1=a[j+2],p2=a[n-j];
			ll p3=n/2-j-1,p4=n/2+j+1;
			if (p1==-1&&p2==-1) {
				fn*=2,fn%=mod;
			} else if (min(p1,p2)==-1) {
				if (max(p1,p2)==p3||max(p1,p2)==p4) {

				} else {
					fn=0;
				}
			} else {
				if (min(p1,p2)==min(p3,p4)&&max(p1,p2)==max(p3,p4)) {

				} else {
					fn=0;
				}
			}
		}

	} else {
		fn=0;
	}
	if (fn)fl[p]=1;
	ans+=fn;
	ans%=mod;
}

bool check(ll *a) {
	ll k=n/2;
	for (ll i=1; i*2-1<=n; i++) {
		if (a[i]!=-1&&a[i]!=k+i)return 0;
		if (n-i+1!=i&&a[n-i+1]!=-1&&a[n-i+1]!=k-i+1)return 0;
	}
	return 1;
}

int main() {
	ll t;
	cin >> t;
	while (t--) {
		cin >> n;

		for (ll i=1; i<=n; i++) {
			cin >> a[i];
		}
		if (n%2==1) {
			ans=0;
			fl[0]=fl[1]=fl[2]=fl[3]=fl[4]=fl[5]=fl[6]=fl[7]=0;
			for (ll O=0; O<4; O++) {
				solve(a,O);

				for (ll i=1; i<=n; i++)b[i]=-1;
				for (ll i=1; i<=n; i++)if (a[i]!=-1)b[n-a[i]+1]=i;
				for (ll i=1; i<=n; i++)a[i]=b[i];
			}
			cout<<(ans-max(0ll,fl[0]+fl[1]-1)-max(0ll,fl[2]+fl[1]-1)-max(0ll,fl[2]+fl[3]-1)-max(0ll,fl[3]+fl[0]-1)+mod)%mod<<"\n";
		} else {
			ans=0;
			fl[0]=fl[1]=fl[2]=fl[3]=fl[4]=fl[5]=fl[6]=fl[7]=0;
			for (ll O=0; O<4; O++) {
				solve2(a,O);
//				cout<< ans<<":";
//				for (ll i=1; i<=n; i++)cout<< a[i]<<",";
//				cout<<"\n";
				for (ll i=1; i<=n; i++)b[i]=-1;
				for (ll i=1; i<=n; i++)if (a[i]!=-1)b[n-a[i]+1]=i;
				for (ll i=1; i<=n; i++)a[i]=b[i];
			}
//			cout<< ans<<"\n";
			ll fn=1;
			for (ll i=0; i<n/2; i++) {
				ll p1=a[i+1],p2=a[n-i];
				ll p3=n/2-i,p4=n/2+i+1;
				if (p1==-1&&p2==-1) {
					fn*=2,fn%=mod;
				} else if (min(p1,p2)==-1) {
					if (max(p1,p2)==p3||max(p1,p2)==p4) {

					} else {
						fn=0;
					}
				} else {
					if (min(p1,p2)==min(p3,p4)&&max(p1,p2)==max(p3,p4)) {

					} else {
						fn=0;
					}
				}
			}
			cout<< (ans+fn-max(0ll,fl[0]+fl[2]+(fn!=0)-1)-max(0ll,fl[1]+fl[3]+(fn!=0)-1)+mod)%mod<<"\n";
		}
	}
	return 0;
}

/*
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
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3584kb

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

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: 30ms

memory: 5704kb

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'