QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #885100 | #9785. Shrooks | piggy123 | WA | 36ms | 5712kb | C++17 | 5.1kb | 2025-02-06 13:42:47 | 2025-02-06 13:42:48 |
Judging History
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)) {
if (p==4&&(a[1]==-1&&a[n]==-1))fn=2;
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;
for (ll O=0; O<4; O++) {
solve(a);
if (check(a))ans--;
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+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
■■■■■ ■■ ■■■ ■■■ ■ ■ ■ ■■■■ ■■■■
■ ■■ ■■ ■ ■■ ■ ■■ ■ ■ ■■ ■ ■■ ■■ ■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■■ ■■ ■■ ■ ■■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■ ■ ■■ ■■
■ ■ ■■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■■ ■ ■■■ ■ ■■■ ■■ ■■ ■■ ■■■
■■■■■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■ ■ ■■
■ ■■ ■■ ■■ ■■ ■■ ■■ ■■ ■ ■■ ■■
■ ■■ ■■■■ ■■■■ ■■ ■■ ■■■■■■ ■■■■
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5712kb
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:
1 4 1 0 6 92
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5708kb
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:
1 4 1 0 6 92
result:
ok 6 numbers
Test #3:
score: -100
Wrong Answer
time: 36ms
memory: 3584kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 998244352 0 0 0 0 0 0 0 0 0 0 0 0 0 0 998244352 0 0 0 0 0 3 0 0 2 0 0 0 0 0 0 0 0 2 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 19th numbers differ - expected: '1', found: '0'