Submission #167436

#	Time	Username	Problem	Language	Result	Execution time	Memory
167436		faremy	Teams (IOI15_teams)	C++14	34 / 100	4013 ms	12024 KiB

teams

#include "teams.h"

#include <algorithm>
#include <queue>


struct Interval
{
	int start, end;
	bool operator <(const Interval &other) const
	{
		return (other.end < end);
	}
};

const int MAXN = 1e5;
int students;

Interval prefer[MAXN];
std::priority_queue<Interval> canAssign;

long long groupSizes[MAXN];


void init(int N, int A[], int B[])
{
	students = N;
	for (int iStud = 0; iStud < students; iStud++)
	{
		prefer[iStud].start = A[iStud];
		prefer[iStud].end = B[iStud];
	}

	std::sort(prefer, prefer + students, [](const Interval &a, const Interval &b) { return (a.start != b.start ? a.start < b.start : a.end < b.end); }); 
}

int can(int M, int K[])
{
	long long sizeSum = 0;
	for (int iGroup = 0; iGroup < M; iGroup++)
	{
		sizeSum += K[iGroup];
		if (sizeSum > students)
			return 0;
	}

	while (!canAssign.empty())
		canAssign.pop();
	std::sort(K, K + M);

	int iStud = 0;
	for (int iGroup = 0; iGroup < M; iGroup++)
	{
		for (; iStud < students && prefer[iStud].start <= K[iGroup]; iStud++)
			canAssign.emplace(prefer[iStud]);
		while (!canAssign.empty() && canAssign.top().end < K[iGroup])
			canAssign.pop();

		if ((int)canAssign.size() < K[iGroup])
			return 0;
		for (int iAssign = 0; iAssign < K[iGroup]; iAssign++)
			canAssign.pop();
	}

	return 1;
}

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