QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #882819 | #9785. Shrooks | Sai_tqwq | WA | 17ms | 5608kb | C++14 | 1.5kb | 2025-02-05 11:40:32 | 2025-02-05 11:40:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
mt19937 rnd(537462565);
const int mod=998244353;
int cas,n,c,a[200009],b[200009],ans[6];
void turn(){
memset(b,-1,sizeof(int)*(n+5));
for(int i=1;i<=n;i++)if(a[i]>=0)b[n-a[i]+1]=i;
memcpy(a,b,sizeof(int)*(n+5));
}
int calc(int x,int xx,int y,int yy){
if((a[x]==y||a[x]==yy||a[x]==-1)+(a[xx]==y||a[xx]==yy||a[xx]==-1)<2)return 0;
if(a[x]!=-1&&a[xx]!=-1&&a[x]==a[xx])return 0;
if((a[x]==-1)+(a[xx]==-1)==2)return 2;
return 1;
}
int f(vector<int> vec){int k=0;for(int x:vec)k+=(!!x);return max(0ll,k-1);}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>cas;
while(cas--){
cin>>n;c=n>>1;
for(int i=1;i<=n;i++)cin>>a[i];
if(n&1){
for(int op:{0,1,2,3}){
if(a[n]!=c+1&&a[n]!=-1)ans[op]=0;
else{
ans[op]=1;
for(int i=0;i<c;i++)
(ans[op]*=calc(c-i,c+1+i,1+i,n-1-i))%=mod;
}
turn();
}
cout<<(ans[0]+ans[1]+ans[2]+ans[3]-f({ans[0],ans[1]})-f({ans[0],ans[3]})-f({ans[2],ans[1]})-f({ans[2],ans[3]}))%mod<<endl;
}else{
for(int op:{0,1,2,3}){
if((a[1]!=c&&a[1]!=-1)||(a[c+1]!=n&&a[c+1]!=-1))ans[op]=0;
else{
ans[op]=1;
for(int i=0;i<c-1;i++)
(ans[op]*=calc(2+i,n-i,c-i-1,c+i+1))%=mod;
}
turn();
}
ans[4]=1;
for(int i=0;i<c;i++)(ans[4]*=calc(1+i,n-i,c-i,c+1+i))%=mod;
cout<<(ans[0]+ans[1]+ans[2]+ans[3]+ans[4]-f({ans[0],ans[2],ans[4]})-f({ans[1],ans[3],ans[4]}))%mod<<endl;
}
}
return 0;
}
詳細信息
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:
1 4 1 0 6 92
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:
1 4 1 0 6 92
result:
ok 6 numbers
Test #3:
score: -100
Wrong Answer
time: 17ms
memory: 5608kb
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 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 14th numbers differ - expected: '0', found: '1'