Submission #289032

#	Time	Username	Problem	Language	Result	Execution time	Memory
289032		user202729	Teams (IOI15_teams)	C++17	34 / 100	4075 ms	12540 KiB

teams

// moreflags=grader.cpp
//
// 10
// :(
#include "teams.h"
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
//#include<cassert>

std::vector<std::pair<int, int>> students;

void init(int N, int A[], int B[]) {
	students.clear(); students.reserve(N);
	for(int i=0; i<N; ++i)
		students.push_back({A[i], B[i]});
	std::sort(begin(students), end(students));
}

int can(int M, int K[]) {
	std::sort(K, K+M);
	std::priority_queue<int, std::vector<int>, std::greater<int>> rights;
	/*
	rights.push(1);
	rights.push(2);
	rights.push(1);
	assert(rights.top()==1); rights.pop();
	assert(rights.top()==1); rights.pop();
	assert(rights.top()==2); rights.pop();
	assert(rights.empty());
	*/
	
	auto iterator=students.begin();
	for(int index=0; index<M; ++index){
		auto const k=K[index];
		while(iterator!=students.end() and iterator->first<=k){
			rights.push(iterator->second);
			++iterator;
		}
		while(not rights.empty() and rights.top()<k)
			rights.pop();

		for(int _=0; _<k; ++_){
			if(rights.empty())
				return 0;
			rights.pop();
		}
	}
	return 1;
}

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