Submission #484870

#	Time	Username	Problem	Language	Result	Execution time	Memory
484870		imachug	Teams (IOI15_teams)	C++17	34 / 100	4085 ms	8888 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);

	vector<bool> disabled(students.size());

	for(int i = 0; i < m; i++) {
		int cnt = 0;
		for(int j = 0; j < students.size(); j++) {
			if(disabled[j]) {
				continue;
			}
			auto [l, r] = students[j];
			if(l <= k[i] && k[i] <= r) {
				cnt++;
				disabled[j] = true;
				if(cnt == k[i]) {
					break;
				}
			}
		}
		if(cnt < k[i]) {
			return 0;
		}
	}

	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:20: 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 |   for(int j = 0; j < students.size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~

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