Submission #484880

#	Time	Username	Problem	Language	Result	Execution time	Memory
484880		imachug	Teams (IOI15_teams)	C++17	21 / 100	4080 ms	8920 KiB

teams

#include "teams.h"


#include <bits/stdc++.h>

using namespace std;


vector<pair<int, int>> students;


void init(int n, int a[], int b[]) {
	for(int i = 0; i < n; i++) {
		students.emplace_back(a[i], b[i]);
	}
	sort(students.begin(), students.end(), [](pair<int, int> p1, pair<int, int> p2) {
		return p1.second < p2.second;
	});
}


int can(int m, int k[]) {
	sort(k, k + m);

	multiset<pair<int, int>> disabled_intervals;

	for(int i = 0; i < m; i++) {
		int l = 0;
		while(l < students.size() && students[l].second < k[i]) {
			l++;
		}

		int cnt = 0;

		int r = l;
		for(; r < students.size(); r++) {
			bool disabled = false;
			for(auto [r1, x1]: disabled_intervals) {
				if(r < r1 && students[r].first <= x1) {
					disabled = true;
				}
			}
			if(disabled) {
				continue;
			}

			if(students[r].first <= k[i]) {
				cnt++;
				if(cnt == k[i]) {
					r++;
					break;
				}
			}
		}

		if(cnt < k[i]) {
			return 0;
		}

		auto it = disabled_intervals.upper_bound(make_pair(r, 0));
		while(it != disabled_intervals.begin() && prev(it)->second <= k[i]) {
			disabled_intervals.erase(prev(it));
		}
		disabled_intervals.insert(make_pair(r, k[i]));
	}

	return 1;

	// multiset<pair<int, int>> projects;
	// for(int i = 0; i < m; i++) {
	// 	projects.insert(make_pair(k[i], k[i]));
	// }

	// for(auto [l, r]: students) {
	// 	auto it = projects.lower_bound(make_pair(l, 0));
	// 	if(it != projects.end() && it->first <= r) {
	// 		auto p = *it;
	// 		projects.erase(it);
	// 		p.second--;
	// 		if(p.second > 0) {
	// 			projects.insert(p);
	// 		}
	// 	}
	// }

	// return projects.empty();
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:29:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   while(l < students.size() && students[l].second < k[i]) {
      |         ~~^~~~~~~~~~~~~~~~~
teams.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(; r < students.size(); r++) {
      |         ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23