Submission #838225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
838225	2023-08-26T11:20:56 Z	fatemetmhr	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	10 / 100	9000 ms	332 KB

festival2

// 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';

}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	3725 ms	300 KB	Output is correct
9	Correct	3697 ms	296 KB	Output is correct
10	Correct	3753 ms	332 KB	Output is correct
11	Correct	5 ms	212 KB	Output is correct
12	Correct	129 ms	212 KB	Output is correct
13	Correct	125 ms	212 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	3725 ms	300 KB	Output is correct
9	Correct	3697 ms	296 KB	Output is correct
10	Correct	3753 ms	332 KB	Output is correct
11	Correct	5 ms	212 KB	Output is correct
12	Correct	129 ms	212 KB	Output is correct
13	Correct	125 ms	212 KB	Output is correct
14	Execution timed out	9056 ms	212 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	3725 ms	300 KB	Output is correct
9	Correct	3697 ms	296 KB	Output is correct
10	Correct	3753 ms	332 KB	Output is correct
11	Correct	5 ms	212 KB	Output is correct
12	Correct	129 ms	212 KB	Output is correct
13	Correct	125 ms	212 KB	Output is correct
14	Execution timed out	9056 ms	212 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	3725 ms	300 KB	Output is correct
9	Correct	3697 ms	296 KB	Output is correct
10	Correct	3753 ms	332 KB	Output is correct
11	Correct	5 ms	212 KB	Output is correct
12	Correct	129 ms	212 KB	Output is correct
13	Correct	125 ms	212 KB	Output is correct
14	Execution timed out	9056 ms	212 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	3725 ms	300 KB	Output is correct
9	Correct	3697 ms	296 KB	Output is correct
10	Correct	3753 ms	332 KB	Output is correct
11	Correct	5 ms	212 KB	Output is correct
12	Correct	129 ms	212 KB	Output is correct
13	Correct	125 ms	212 KB	Output is correct
14	Execution timed out	9056 ms	212 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-