結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー メイト
提出日時 2026-02-02 14:16:30
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,662 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,229 ms
コンパイル使用メモリ 223,288 KB
実行使用メモリ 16,584 KB
最終ジャッジ日時 2026-02-02 14:16:35
合計ジャッジ時間 4,525 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define M 200005
#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
int n,a[M],l[M],r[M],o[M],t[M][2],f[M],s[M];
vector<int>c[M];
mint F[M],iF[M];
void d(int x){l[r[x]]=l[x];r[l[x]]=r[x];}
mint C(int n,int k){return n>=k&&k>=0?F[n]*iF[k]*iF[n-k]:0;}
void D(int u){s[u]=1;for(int v:c[u])D(v),s[u]+=s[v];}
int main(){
	scanf("%d",&n);
	F[0]=1;for(int i=1;i<=n;i++)F[i]=F[i-1]*i;
	iF[n]=F[n].inv();for(int i=n;i;i--)iF[i-1]=iF[i]*i;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		l[i]=i-1;r[i]=i+1;
		t[i][0]=l[i]>=1?l[i]:-1;
		t[i][1]=r[i]<=n?r[i]:-1;
	}
	queue<int>q;
	for(int i=1;i<=n;i++)if(!a[i])q.push(i),d(i);
	int T=0,O=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		if(T>=n-1){O=0;break;}
		o[x]=++T;
		t[x][0]=l[x]>=1?l[x]:-1;
		t[x][1]=r[x]<=n?r[x]:-1;
		if(l[x]>=1){if(!a[l[x]]){O=0;break;}a[l[x]]--;if(!a[l[x]]){if(T<n-1)q.push(l[x]),d(l[x]);else{O=0;break;}}}
		if(O&&r[x]<=n){if(!a[r[x]]){O=0;break;}a[r[x]]--;if(!a[r[x]]){if(T<n-1)q.push(r[x]),d(r[x]);else{O=0;break;}}}
	}
	if(T!=n-1||!O){puts("0");return 0;}
	int cnt=0;for(int i=1;i<=n;i++)if(o[i])cnt++;
	if(cnt!=n-1){puts("0");return 0;}
	for(int i=1;i<=n;i++)if(t[i][0]>=0||t[i][1]>=0)f[i]=t[i][0]<0?t[i][1]:t[i][1]<0?t[i][0]:(o[t[i][0]]<o[t[i][1]]?t[i][1]:t[i][0]);
	int R=0;for(int i=1;i<=n;i++)if(!o[i])R=i;
	if(!R){puts("0");return 0;}
	for(int i=1;i<=n;i++)if(f[i])c[f[i]].push_back(i);
	D(R);
	mint A=1;for(int i=1;i<=n;i++)if(t[i][0]>=0&&t[i][1]>=0)A*=C(s[t[i][0]]+s[t[i][1]],s[t[i][0]]);
	long long v=A.val();
	v=(v%998244353LL+998244353LL)%998244353LL;
	printf("%d\n",(int)v);
}
0