Submission #524908

#	Time	Username	Problem	Language	Result	Execution time	Memory
524908		amunduzbaev	Event Hopping 2 (JOI21_event2)	C++17	1 / 100	56 ms	1868 KiB

event2

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k; cin>>n>>k;
	vector<ar<int, 2>> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1];
	}
	
	vector<int> res = {(int)1e9};
	for(int mask=0;mask < (1 << n);mask++){
		if(__builtin_popcount(mask) != k) continue;
		vector<int> p;
		for(int j=0;j<n;j++){
			if(mask >> j & 1) p.push_back(j);
		}
		
		sort(p.begin(), p.end(), [&](int i, int j){
			return a[i][0] < a[j][0];
		});
		
		bool ok = 1;
		for(int i=1;i<k;i++){
			if(a[p[i-1]][1] > a[p[i]][0]) ok = 0;
		}
		
		if(ok){
			sort(p.begin(), p.end());
			res = min(res, p);
		}
	}
	
	if(res[0] == 1e9){
		cout<<-1<<"\n";
	} else {
		for(auto x : res) cout<<x + 1<<"\n";
	}
}

• Subtask 1: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61