Submission #45560

#	Time	Username	Problem	Language	Result	Execution time	Memory
45560		maksim_gaponov	Port Facility (JOI17_port_facility)	C++14	10 / 100	685 ms	932 KiB

port_facility

#define _CRT_SECURE_NO_WARNINGS
#ifdef _DEBUG
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;

void openFiles() {
#ifdef _DEBUG
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

struct Action {
	int id;
	int time;
	bool type;

	Action(int id, int time, bool type) : id(id), time(time), type(type) {}
};

bool operator<(const Action& a1, const Action& a2) {
	return a1.time < a2.time;
}

bool get_bit(int mask, int i) {
	return mask & (1 << i);
}

vector<Action> actions;

bool ok(int mask) {
	vector<int> a[2];
	for (auto act : actions) {
		if (act.type) {
			a[(int)get_bit(mask, act.id)].push_back(act.id);
		}
		else {
			if (a[(int)get_bit(mask, act.id)].back() != act.id)
				return false;
			a[(int)get_bit(mask, act.id)].pop_back();
		}
	}
	return true;
}

int main() {
	openFiles();
	IOoptimize();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int time1, time2;
		cin >> time1 >> time2;
		actions.push_back(Action(i, time1, true));
		actions.push_back(Action(i, time2, false));
	}
	sort(actions.begin(), actions.end());
	ll ans = 0;
	for (int mask = 0; mask < (1 << n); mask++) {
		if (ok(mask))
			ans = (ans + 1) % mod;
	}
	cout << ans;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22