結果

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

ソースコード

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]=t[i][1]=-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();o[x]=++T;
		if(l[x]>=1){if(!a[l[x]]){O=0;break;}t[x][0]=l[x];a[l[x]]--;if(!a[l[x]])q.push(l[x]),d(l[x]);}
		if(r[x]<=n){if(!a[r[x]]){O=0;break;}t[x][1]=r[x];a[r[x]]--;if(!a[r[x]])q.push(r[x]),d(r[x]);}
		if(!O||T==n-1)break;
	}
	if(T!=n-1||!O){puts("0");return 0;}
	int R=0;for(int i=1;i<=n;i++)if(!o[i])R=i;
	o[R]=n;
	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]);
	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(c[i].size()==2)A*=C(s[c[i][0]]+s[c[i][1]],s[c[i][0]]);
	printf("%d\n",A.val());
}
0