QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#884914	#9785. Shrooks	AllenJYL	WA	17ms	5868kb	C++14	4.6kb	2025-02-06 11:46:26	2025-02-06 11:46:28

Judging History

This is the latest submission verdict.

[2025-02-06 11:46:28]
Judged

Verdict: WA
Time: 17ms
Memory: 5868kb

Show

[2025-02-06 11:46:26]
Submitted

answer

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

#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define all(_array) (_array).begin(),(_array).end()
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define TAK cout<<"TAK"<<endl
#define NIE cout<<"NIE"<<endl
#define OK cerr<<"OK"<<endl
#define pii pair<int,int>
#define endl '\n'

bool bg_memory;
mt19937 rnd(time(0));
int Case=1;
const int mod=998244353;
const int inf=2147483647;
const int bs=233;
const double eps=1e-6;
const int N=2e5+7,M=1e5+7;

template<class _t1,class _t2>inline void cmax(_t1 &a,_t2 b){a=a<b?b:a;}
template<class _t1,class _t2>inline void cmin(_t1 &a,_t2 b){a=a>b?b:a;}
inline int qp(int a,int b,int p=mod){int res=1;while(b){if(b&1)res=1ll*res*a%p;a=1ll*a*a%p;b>>=1;}return res;}
inline int sqrt(int x,int r){int l=0,ans=0;while(l<=r){if(1ll*mid*mid<=x) ans=mid,l=mid+1;else r=mid-1;}return ans;}

int n;
int a[N],b[N];
int ans,cnt;
bool fl;
bool chk(int x,int y){
    return (a[x]==-1||a[x]==y)&&(b[y]==-1||b[y]==x);
}
int ask(int u,int d,int l,int r){
    return (chk(u,l)&chk(d,r))+(chk(u,r)&chk(d,l));
}

void Main(){
    
    cin>>n;
    for(int i=1;i<=n;i++) b[i]=-1;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]>0?b[a[i]]=i:0;
    ans=0;
    if(n&1){
        cnt=chk(1,(n+1)/2);
        for(int i=2;i<=(n+1)/2;i++) (cnt*=ask(i,n+1-i,(n+1)/2-(i-1),(n+1)/2+(i-1)))%=mod;
        (ans+=cnt)%=mod;
        cnt=chk((n+1)/2,n);
        for(int i=n-1;i>=(n+1)/2;i--) (cnt*=ask((n+1)/2-(n-i),(n+1)/2+(n-i),n-i,i))%=mod;
        (ans+=cnt)%=mod;
        cnt=chk(n,(n+1)/2);
        for(int i=n-1;i>=(n+1)/2;i--) (cnt*=ask(n-i,i,(n+1)/2-(n-i),(n+1)/2+(n-i)))%=mod;
        (ans+=cnt)%=mod;
        cnt=chk((n+1)/2,1);
        for(int i=2;i<=(n+1)/2;i++) (cnt*=ask((n+1)/2-(i-1),(n+1)/2+(i-1),i,n+1-i))%=mod;
        (ans+=cnt)%=mod;
        cnt=1;
        for(int i=1;i<=(n+1)/2;i++) cnt&=chk(i,(n+1)/2+(i-1));
        for(int i=n;i>(n+1)/2;i--) cnt&=chk(i,(n+1)/2-(n+1-i));
        (ans+=mod-cnt)%=mod;
        cnt=1;
        for(int i=1;i<=(n+1)/2;i++) cnt&=chk(i,(n+1)/2-(i-1));
        for(int i=n;i>(n+1)/2;i--) cnt&=chk(i,(n+1)/2+(n+1-i));
        (ans+=mod-cnt)%=mod;
        cnt=1;
        for(int i=1;i<(n+1)/2;i++) cnt&=chk(i,(n+1)/2+i);
        for(int i=n;i>=(n+1)/2;i--) cnt&=chk(i,(n+1)/2-(n-i));
        (ans+=mod-cnt)%=mod;
        cnt=1;
        for(int i=1;i<(n+1)/2;i++) cnt&=chk(i,(n+1)/2-i);
        for(int i=n;i>=(n+1)/2;i--) cnt&=chk(i,(n+1)/2+(n-i));
        (ans+=mod-cnt)%=mod;
    }else{
        cnt=chk(1,n/2)&chk(n/2+1,n);
        for(int i=2;i<=n/2;i++) (cnt*=ask(i,n+2-i,n/2-(i-1),n/2+(i-1)))%=mod;
        (ans+=cnt)%=mod;
        cnt=chk(n,n/2)&chk(n/2,n);
        for(int i=n-1;i>n/2;i--) (cnt*=ask(n/2-(n-i),n/2+(n-i),n-i,i))%=mod;
        (ans+=cnt)%=mod;
        cnt=chk(n,n/2+1)&chk(n/2,1);
        for(int i=n-1;i>n/2;i--) (cnt*=ask(n-i,i,n/2+1-(n-i),n/2+1+(n-i)))%=mod;
        (ans+=cnt)%=mod;
        cnt=chk(1,n/2+1)&chk(n/2+1,1);
        for(int i=2;i<=n/2;i++) (cnt*=ask(i,n+2-i,n/2+1-(i-1),n/2+1+(i-1)))%=mod;
        (ans+=cnt)%=mod;
        cnt=1;
        for(int i=1;i<=n/2;i++) cnt&=chk(i,n/2+i);
        for(int i=n;i>n/2;i--) cnt&=chk(i,n/2-(n-i));
        (ans+=mod-cnt*2)%=mod;
        cnt=1;
        for(int i=1;i<=n/2;i++) cnt&=chk(i,n/2-(i-1));
        for(int i=n;i>n/2;i--) cnt&=chk(i,n/2+(n+1-i));
        (ans+=mod-cnt*2)%=mod;
        cnt=1;
        for(int i=1;i<=n/2;i++) (cnt*=ask(i,n+1-i,n/2-(i-1),n/2+i))%=mod;
        (ans+=cnt)%=mod;

    }
    cout<<ans<<endl;
    if(fl) cout<<"CURN:"<<n<<endl;

    return;
}
string RdFile="";
bool en_memory;

signed main(){
    auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
    // freopen((RdFile+".in").c_str(),"r",stdin);
    // freopen((RdFile+".out").c_str(),"w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>Case;
    if(Case==21874) fl=1;
    while(Case--) Main();
    auto en_clock=chrono::high_resolution_clock::now();
    auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
    double duration_count=duration_clock.count()*0.001;
    double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
    // cerr<<"Time:"<<duration_count<<"ms"<<endl;
    // cerr<<"Memory: "<<memory_used<<"MB"<<endl;
    return 0;
}

Source code, Language: C++14

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

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

memory: 5868kb

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'