結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー kotatsugame
提出日時 2025-11-17 23:36:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 2,215 bytes
コンパイル時間 983 ms
コンパイル使用メモリ 84,488 KB
実行使用メモリ 42,056 KB
最終ジャッジ日時 2025-11-17 23:36:10
合計ジャッジ時間 4,145 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:126:21: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  126 |                 auto[l,r]=pr[u];
      |                     ^

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#include<cassert>
#include<atcoder/modint>
using namespace std;
#include<vector>
template<typename T>
struct combination{
	vector<T>fac,ifac;
	combination(size_t N=0):fac(1,1),ifac(1,1)
	{
		make_table(N);
	}
	void make_table(size_t N)
	{
		if(fac.size()>N)return;
		size_t now=fac.size();
		N=max(N,now*2);
		fac.resize(N+1);
		ifac.resize(N+1);
		for(size_t i=now;i<=N;i++)fac[i]=fac[i-1]*i;
		ifac[N]=1/fac[N];
		for(size_t i=N;i-->now;)ifac[i]=ifac[i+1]*(i+1);
	}
	T factorial(size_t n)
	{
		make_table(n);
		return fac[n];
	}
	T invfac(size_t n)
	{
		make_table(n);
		return ifac[n];
	}
	T P(size_t n,size_t k)
	{
		if(n<k)return 0;
		make_table(n);
		return fac[n]*ifac[n-k];
	}
	T C(size_t n,size_t k)
	{
		if(n<k)return 0;
		make_table(n);
		return fac[n]*ifac[n-k]*ifac[k];
	}
	T H(size_t n,size_t k)
	{
		if(n==0)return k==0?1:0;
		return C(n-1+k,k);
	}
};
using mint=atcoder::modint998244353;
combination<mint>C;
int N;
int A[2<<17];
vector<int>G[2<<17];
pair<int,int>pr[2<<17];
int ord[2<<17];
pair<int,mint>dfs(int u)
{
	int sz=0;
	mint ret=1;
	for(int v:G[u])
	{
		auto t=dfs(v);
		ret*=t.second;
		ret*=C.C(sz+t.first,t.first);
		sz+=t.first;
	}
	return make_pair(sz+1,ret);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	vector<int>Q;
	set<int>E;
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		if(A[i]==0)Q.push_back(i);
		E.insert(i);
		pr[i]=make_pair(-1,-1);
	}
	for(int i=0;i<Q.size();i++)
	{
		int u=Q[i];
		ord[u]=i;
		auto it=E.find(u);
		assert(it!=E.end());
		it=E.erase(it);
		if(it!=E.begin())
		{
			int l=*prev(it);
			if(A[l]==0)
			{
				cout<<0<<endl;
				return 0;
			}
			pr[u].first=l;
			if(!--A[l])Q.push_back(l);
		}
		if(it!=E.end())
		{
			int r=*it;
			if(A[r]==0)
			{
				cout<<0<<endl;
				return 0;
			}
			pr[u].second=r;
			if(!--A[r])Q.push_back(r);
		}
	}
	if(!E.empty())
	{
		cout<<0<<endl;
		return 0;
	}
	int root=-1;
	for(int u=0;u<N;u++)
	{
		auto[l,r]=pr[u];
		if(l==-1&&r==-1)
		{
			assert(root==-1);
			root=u;
		}
		else if(l==-1)G[r].push_back(u);
		else if(r==-1)G[l].push_back(u);
		else G[ord[l]<ord[r]?l:r].push_back(u);
	}
	assert(root!=-1);
	cout<<dfs(root).second.val()<<"\n";
}
0