Submission #1026719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026719		Unforgettablepl	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	10 / 100	9008 ms	460 KiB

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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 27
• Subtask 4: 0 / 14
• Subtask 5: 0 / 36
• Subtask 6: 0 / 13