Submission #60697

#	Time	Username	Problem	Language	Result	Execution time	Memory
60697		Eae02	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	412 ms	525312 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>
#include <set>

long long delivery(int numTeams, int capacity, int numSections, int p[])
{
	auto DistTo0 = [&] (int x)
	{
		return std::min(x, numSections - x);
	};
	
	int numL = 0;
	int numR = 0;
	
	std::vector<int> numTeamsPerSection(numSections);
	
	std::set<int> teamPositions;
	for (int i = 0; i < numTeams; i++)
	{
		if (p[i] != 0)
		{
			numTeamsPerSection[p[i]]++;
			if (p[i] * 2 < numSections)
				numL++;
			else
				numR++;
		}
	}
	
	long long sec = 0;
	
	while (numL > 0 || numR > 0)
	{
		int boxes = capacity;
		int pos = 0;
		int dir;
		
		if (numR > numL)
		{
			dir = -1;
		}
		else
		{
			dir = 1;
		}
		
		while (true)
		{
			if (pos != 0)
			{
				int numToGive = std::min(numTeamsPerSection[pos], boxes);
				numTeamsPerSection[pos] -= numToGive;
				boxes -= numToGive;
				
				if (pos * 2 < numSections)
					numL -= numToGive;
				else
					numR -= numToGive;
				
				if (boxes <= 0 || (numL == 0 && numR == 0))
				{
					sec += DistTo0(pos);
					break;
				}
			}
			
			pos += dir;
			sec++;
			if (pos == 0 || pos == numSections)
				break;
			if (pos == -1)
				pos = numSections - 1;
		}
	}
	
	return sec;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30