結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー tokitsukaze
提出日時 2026-01-22 15:06:09
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 1,461 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,227 ms
コンパイル使用メモリ 220,904 KB
実行使用メモリ 11,112 KB
最終ジャッジ日時 2026-01-22 15:06:13
合計ジャッジ時間 3,557 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const int MAX=2e5+10;
#include<atcoder/modint>
using mint=atcoder::modint998244353;
int ord[MAX],id[MAX],fa[MAX],sz[MAX],to[MAX][2];
int a[MAX],l[MAX],r[MAX];
void del(int x)
{
	l[r[x]]=l[x];
	r[l[x]]=r[x];
}
int main()
{
	int n,i,ok,x,tot;
	mint fz,fm;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		l[i]=i-1;
		r[i]=i+1;
		fa[i]=0;
		sz[i]=1;
		to[i][0]=to[i][1]=-1;
	}
	queue<int> q;
	for(i=1;i<=n;i++)
	{
		if(a[i]==0)
		{
			q.push(i);
			del(i);
		}
	}
	ok=1;
	tot=0;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		ord[x]=++tot;
		id[tot]=x;
		if(l[x]>=1)
		{
			if(a[l[x]]==0)
			{
				ok=0;
				break;
			}
			to[x][0]=l[x];
			a[l[x]]--;
			if(a[l[x]]==0)
			{
				q.push(l[x]);
				del(l[x]);
			}
		}
		if(r[x]<=n)
		{
			if(a[r[x]]==0)
			{
				ok=0;
				break;
			}
			to[x][1]=r[x];
			a[r[x]]--;
			if(a[r[x]]==0)
			{
				q.push(r[x]);
				del(r[x]);
			}
		}
	}
	if(tot!=n) ok=0;
	if(ok==0)
	{
		puts("0");
		return 0;
	}
	for(i=1;i<=n;i++)
	{
		if(to[i][0]==-1 && to[i][1]==-1) continue;
		if(to[i][0]==-1) fa[i]=to[i][1];
		else if(to[i][1]==-1) fa[i]=to[i][0];
		else
		{
			if(ord[to[i][0]]<ord[to[i][1]]) fa[i]=to[i][0];
			else fa[i]=to[i][1];
		}
	}
	for(i=1;i<=n;i++) sz[fa[id[i]]]+=sz[id[i]];
	fz=fm=1;
	for(i=1;i<=n;i++)
	{
		fz*=i;
		fm*=sz[i];
	}
	printf("%d\n",fz/fm);
	return 0;
}
0