Submission #838225

#TimeUsernameProblemLanguageResultExecution timeMemory
838225fatemetmhrFestivals in JOI Kingdom 2 (JOI23_festival2)C++17
10 / 100
9056 ms332 KiB
// na hanooz omidi vjood dare... hanooz ye karayi hast ke bknm :)

#include <bits/stdc++.h>

using namespace std;


#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   (x).begin(), (x).end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const int maxn5 = 100;

int mod, n, pt = 0;
ll ans = 0;
pair <int, int> mt[maxn5];
bool mark[maxn5];

int find_greedy(){
	int mx = -1, cnt = 0;
	for(int i = 0; i < pt; i++){
		if(mx < mt[i].fi){
			cnt++;
			mx = mt[i].se;
		}
	}
	return cnt;
}

int find_best(){
	int mx = 0;
	for(int mask = 0; mask < (1 << pt); mask++){
		bool re = true;
		for(int i = 0; i < pt && re; i++) if((mask >> i)&1)
			for(int j = i + 1; j < pt && re; j++) if((mask >> j)&1)
				re &= (mt[i].se < mt[j].fi);
		if(re)
			mx = max(mx, __builtin_popcount(mask));
	}
	return mx;
}


void solve(){
	if(pt * 2 == n){
		ans += (find_greedy() < find_best());
		return;
	}
	for(int i = 0; i < n; i++) if(!mark[i]){
		mark[i] = true;
		mt[pt].fi = i;
		for(int j = i + 1; j < n; j++) if(!mark[j]){
			mt[pt++].se = j;
			mark[j] = true;
			solve();
			mark[j] = false;
			pt--;
		}
		mark[i] = false;
		return;
	}
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	
	cin >> n >> mod;
	n *= 2;

	solve();

	cout << ans % mod << '\n';

}





















#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...