#468106 (C++14) No.562 超高速一人かるた small

• 問題: No.562 超高速一人かるた small
• ユーザー: kotatsugame
• 提出日時: 2020-04-22 17:03:03
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 349 ms / 3,000 ms
• コード長: 996 bytes
• コンパイル時間: 974 ms
• コンパイル使用メモリ: 81,144 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-11 20:30:19
• 合計ジャッジ時間: 6,078 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	4 ms; 5,248 KB
testcase_08	AC	43 ms; 5,248 KB
testcase_09	AC	347 ms; 5,248 KB
testcase_10	AC	84 ms; 5,248 KB
testcase_11	AC	172 ms; 5,248 KB
testcase_12	AC	43 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	349 ms; 5,248 KB
testcase_15	AC	348 ms; 5,248 KB
testcase_16	AC	348 ms; 5,248 KB
testcase_17	AC	347 ms; 5,248 KB
testcase_18	AC	347 ms; 5,248 KB
testcase_19	AC	348 ms; 5,248 KB
testcase_20	AC	347 ms; 5,248 KB
testcase_21	AC	347 ms; 5,248 KB
testcase_22	AC	348 ms; 5,248 KB
testcase_23	AC	349 ms; 5,248 KB

コンパイルメッセージ

main.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main()
      | ^~~~

ソースコード

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const long mod=1e9+7;
int N;
string s[20];
int h[20];
long ans[20];
main()
{
	cin>>N;
	for(int i=0;i<N;i++)cin>>s[i];
	sort(s,s+N);
	for(int i=0;i<N-1;i++)
	{
		int j=0;
		while(j<s[i].size()&&j<s[i+1].size()&&s[i][j]==s[i+1][j])j++;
		h[i]=j+1;
	}
	for(int i=1;i<1<<N;i++)
	{
		vector<pair<int,int> >fd;
		for(int j=0;j<N;j++)
		{
			if(i>>j&1)fd.push_back(make_pair(j,0));
		}
		int rest=fd.size();
		if(rest==1)
		{
			(ans[N-rest]+=1)%=mod;
			continue;
		}
		for(int j=0;j+1<fd.size();j++)
		{
			int cummin=1e9;
			for(int k=fd[j].first;k<fd[j+1].first;k++)cummin=min(cummin,h[k]);
			fd[j].second=cummin;
		}
		for(int j=0;j<fd.size();j++)
		{
			int L=j==0?1:fd[j-1].second;
			int R=j+1<fd.size()?fd[j].second:1;
			(ans[N-rest]+=L<R?R:L)%=mod;
		}
	}
	long P=1;
	for(int i=0;i<N-1;i++)
	{
		P=P*(i+1)%mod;
		(ans[i+1]*=P)%=mod;
		(ans[i+1]+=ans[i]*(N-1-i))%=mod;
	}
	for(int i=0;i<N;i++)cout<<ans[i]<<endl;
}