Submission #167430

# Submission time Handle Problem Language Result Execution time Memory
167430 2019-12-08T14:39:21 Z faremy Teams (IOI15_teams) C++14
0 / 100
4000 ms 16636 KB
#include "teams.h"

#include <algorithm>
#include <numeric>
#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;


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[])
{
	if (std::accumulate(K, K + M, 0) > students)
		return 0;

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

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

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

	return 1;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 19 ms 3064 KB Output is correct
2 Correct 42 ms 3128 KB Output is correct
3 Incorrect 32 ms 4232 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 26 ms 3856 KB Output is correct
2 Correct 26 ms 3796 KB Output is correct
3 Execution timed out 4090 ms 4464 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 16636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -