Submission #1026719

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1026719	2024-07-18T09:34:29 Z	Unforgettablepl	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	10 / 100	9000 ms	460 KB

festival2

#include <bits/stdc++.h>
using namespace std;

#define int long long

int ans,n,p;

void check(vector<pair<int,int>> ranges){
	sort(ranges.begin(),ranges.end());
	int last = 0;
	int curr = 0;
	for(auto&[a,b]:ranges){
		if(a<last)continue;
		last = b;
		curr++;
	}
	for(auto&[a,b]:ranges)swap(a,b);
	sort(ranges.begin(),ranges.end());
	last = 0;
	for(auto&[a,b]:ranges){
		if(b<last)continue;
		last = a;
		curr--;
	}
	if(curr<0)ans++;
}

void calc(int x,vector<pair<int,int>> ranges,int halfopen=0){
	if(x==2*n+1){
		check(ranges);
		return;
	}
	if(2*n-x>halfopen){
		ranges.emplace_back(x,-1);
		calc(x+1,ranges,halfopen+1);
		ranges.erase(--ranges.end());
	}
	for(int i=0;i<ranges.size();i++){
		if(ranges[i].second!=-1)continue;
		ranges[i].second=x;
		calc(x+1,ranges,halfopen-1);
		ranges[i].second=-1;	
	}
}


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> p;
	calc(1,{});
	cout << ans << '\n';
}

Compilation message

festival2.cpp: In function 'void calc(long long int, std::vector<std::pair<long long int, long long int> >, long long int)':
festival2.cpp:38:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0;i<ranges.size();i++){
      |              ~^~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

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

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	357 ms	348 KB	Output is correct
9	Correct	354 ms	348 KB	Output is correct
10	Correct	351 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	29 ms	456 KB	Output is correct
13	Correct	29 ms	348 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	357 ms	348 KB	Output is correct
9	Correct	354 ms	348 KB	Output is correct
10	Correct	351 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	29 ms	456 KB	Output is correct
13	Correct	29 ms	348 KB	Output is correct
14	Execution timed out	9008 ms	348 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	357 ms	348 KB	Output is correct
9	Correct	354 ms	348 KB	Output is correct
10	Correct	351 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	29 ms	456 KB	Output is correct
13	Correct	29 ms	348 KB	Output is correct
14	Execution timed out	9008 ms	348 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	357 ms	348 KB	Output is correct
9	Correct	354 ms	348 KB	Output is correct
10	Correct	351 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	29 ms	456 KB	Output is correct
13	Correct	29 ms	348 KB	Output is correct
14	Execution timed out	9008 ms	348 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	357 ms	348 KB	Output is correct
9	Correct	354 ms	348 KB	Output is correct
10	Correct	351 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	29 ms	456 KB	Output is correct
13	Correct	29 ms	348 KB	Output is correct
14	Execution timed out	9008 ms	348 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-