Submission #417200

#	Time	Username	Problem	Language	Result	Execution time	Memory
417200		pavement	Event Hopping 2 (JOI21_event2)	C++17	1 / 100	80 ms	1832 KiB

event2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, K, L[500005], R[500005];
vector<int> ans;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> L[i] >> R[i];
	for (int i = 0; i < (1 << N); i++) {
		if (__builtin_popcountll(i) != K) continue;
		vector<iii> tmp;
		for (int j = 0; j < N; j++)
			if (i & (1 << j)) tmp.eb(L[j + 1], R[j + 1], j + 1);
		sort(tmp.begin(), tmp.end());
		bool inv = 0;
		for (int i = 1; i < tmp.size(); i++)
			if (g0(tmp[i]) < g1(tmp[i - 1])) inv = 1;
		if (!inv) {
			vector<int> out;
			for (int i = 0; i < tmp.size(); i++) out.pb(g2(tmp[i]));
			sort(out.begin(), out.end());
			if (ans.empty()) ans = out;
			else ans = min(ans, out);
		}
	}
	if (ans.empty()) cout << "-1\n";
	else for (int i : ans) cout << i << '\n';
}

Compilation message (stderr)

event2.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main() {
      | ^~~~
event2.cpp: In function 'int main()':
event2.cpp:43:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 1; i < tmp.size(); i++)
      |                   ~~^~~~~~~~~~~~
event2.cpp:47:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for (int i = 0; i < tmp.size(); i++) out.pb(g2(tmp[i]));
      |                    ~~^~~~~~~~~~~~

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