UVa 12108

Extraordinarily Tired Students.cpp

#include <queue>
#include <stdio.h>
#include <vector>

using namespace std;

constexpr auto AWAKE = 1;
constexpr auto SLEEP = 0;

struct Student
{
	int awakePeriod;
	int currentCondition;
	int totalPeriod;
};

struct OrderItem
{
	int index;
	int minute;
};

inline bool operator<(const OrderItem &item1, const OrderItem &item2)
{
	return item1.minute > item2.minute;
}

vector<Student> StudentList;
vector<int> TotoalAwakeStudent;
vector<int> StudentRecordTable[10];

int calculateStatus(const Student &student)
{
	return (student.currentCondition < student.awakePeriod) ? AWAKE : SLEEP;
}

void moveToNextStatus(Student &student)
{
	student.currentCondition = (student.currentCondition + 1) % student.totalPeriod;
}

bool isAvailableFallSleepAt(int minute)
{
	return (StudentList.size() - TotoalAwakeStudent[minute]) > TotoalAwakeStudent[minute];
}

vector<int> recordRelativePosition()
{
	auto relativePositionOffset = vector<int> {0};
	for (auto index = 1; index < StudentList.size(); index++)
	{
		relativePositionOffset.push_back(StudentRecordTable[0].size() - StudentRecordTable[index].size());
	}
	return move(relativePositionOffset);
}

bool isNeverAllStudentAwake(const vector<int> &basePositionOffset)
{
	return basePositionOffset == recordRelativePosition();
}

void updateAwakeStudentTable(int index, int status)
{
	int enoughQuantity = StudentRecordTable[index].size() - TotoalAwakeStudent.size();
	for (auto i = 0; i <= enoughQuantity; i++)
	{
		TotoalAwakeStudent.push_back(0);
	}
	TotoalAwakeStudent[StudentRecordTable[index].size() - 1] += status;
}

void addNewPeriodRecord(int studentIndex)
{
	auto isStudentAlreadyAwake = false;
	while (true)
	{
		auto currentStatus = calculateStatus(StudentList[studentIndex]);
		if (isStudentAlreadyAwake && currentStatus == SLEEP)
		{
			break;
		}

		StudentRecordTable[studentIndex].push_back(currentStatus);
		updateAwakeStudentTable(studentIndex, currentStatus);
		moveToNextStatus(StudentList[studentIndex]);
		isStudentAlreadyAwake = (currentStatus == AWAKE);
	}
}

std::priority_queue<OrderItem> prepareOderQueue()
{
	auto orderQueue = priority_queue<OrderItem>();
	for (auto index = 0; index < StudentList.size(); index++)
	{
		addNewPeriodRecord(index);
		int minute = StudentRecordTable[index].size();
		orderQueue.push(OrderItem {index, minute - 1});
	}
	return move(orderQueue);
}

int solve()
{
	auto orderQueue = prepareOderQueue();
	auto basePositionOffset = recordRelativePosition();

	auto minute = orderQueue.top().minute;
	while (TotoalAwakeStudent[minute] != StudentList.size())
	{
		auto index = orderQueue.top().index;
		StudentList[index].currentCondition = isAvailableFallSleepAt(minute) ? StudentList[index].currentCondition : 0;
		addNewPeriodRecord(index);
		orderQueue.push(OrderItem {index, static_cast<int>(StudentRecordTable[index].size()) - 1});

		if (isNeverAllStudentAwake(basePositionOffset))
		{
			return -1;
		}

		orderQueue.pop();
		minute = orderQueue.top().minute;
	}

	return minute + 1;
}

void initialize(int totalStudent)
{
	TotoalAwakeStudent.clear();
	StudentList.resize(totalStudent);
	for (auto &studentRecord: StudentRecordTable)
	{
		studentRecord.clear();
	}
}

int main()
{
	auto n = 0, T = 1;
	while (~scanf("%d", &n))
	{
		if (n == 0)
		{
			break;
		}

		initialize(n);
		for (auto i = 0; i < n; i++)
		{
			auto awakePeriod = 0, sleepPeriod = 0, initialCondition = 0;
			scanf("%d%d%d", &awakePeriod, &sleepPeriod, &initialCondition);
			StudentList[i] = Student {awakePeriod, initialCondition - 1, awakePeriod + sleepPeriod};
		}

		printf("Case %d: %d\n", T++, solve());
	}
	return 0;
}