Submission #484884

#	Time	Username	Problem	Language	Result	Execution time	Memory
484884		imachug	Teams (IOI15_teams)	C++17	34 / 100	4049 ms	9388 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);
	
	long long total = 0;
	for(int i = 0; i < m; i++) {
		total += k[i];
	}
	if(total > students.size()) {
		return 0;
	}

	multiset<pair<int, int>> disabled_intervals;
	disabled_intervals.emplace(students.size() + 1, 0);

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

		while(disabled_intervals.begin()->first <= l) {
			disabled_intervals.erase(disabled_intervals.begin());
		}


		int cnt = 0;

		int r = l;

		for(auto [r1, x]: disabled_intervals) {
			// search in range r..r1
			while(cnt < k[i] && r < r1) {
				if(students[r].first > x && students[r].first <= k[i]) {
					cnt++;
				}
				r++;
			}
			if(cnt == k[i]) {
				break;
			}
		}

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

		while(disabled_intervals.begin()->first <= r && disabled_intervals.begin()->second <= k[i]) {
			disabled_intervals.erase(disabled_intervals.begin());
		}
		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: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if(total > students.size()) {
      |     ~~~~~~^~~~~~~~~~~~~~~~~
teams.cpp:38: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]
   38 |   while(l < students.size() && students[l].second < k[i]) {
      |         ~~^~~~~~~~~~~~~~~~~

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