結果

問題 No.1378 Flattening
ユーザー leaf_1415
提出日時 2020-10-14 19:51:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 746 bytes
コンパイル時間 967 ms
コンパイル使用メモリ 69,572 KB
実行使用メモリ 148,352 KB
最終ジャッジ日時 2024-07-20 19:22:45
合計ジャッジ時間 4,209 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1
other -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cassert>
#include <algorithm>
#include <set>
#include <string>
#define llint long long
#define mod 998244353

using namespace std;

llint n;
llint a[5005], b[5005];
set<string> S;

string s;
void dfs()
{
	if(S.count(s)) return;
	S.insert(s);
	for(int i = 1; i < s.size(); i++){
		if(s[i-1] == s[i]) continue;
		char x = s[i-1], y = s[i];
		s[i-1] = s[i] = min(x, y);
		dfs();
		s[i-1] = x, s[i] = y;
	}
}

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	assert(n >= 1 && n <= 5000);
	for(int i = 1; i <= n; i++) b[i] = a[i];
	sort(b+1, b+n+1);
	for(int i = 1; i <= n; i++) assert(b[i] == i);
	
	
	for(int i = 1; i <= n; i++) s += a[i]+'0';
	
	dfs();
	cout << S.size() << endl;
	
	return 0;
}
0