Submission #60725

#	Time	Username	Problem	Language	Result	Execution time	Memory
60725		Eae02	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	2 ms	380 KiB

boxes

#include "boxes.h"

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

long long delivery(int numTeams, int capacity, int numSections, int p[])
{
	std::sort(p, p + numTeams);
	
	auto DistTo0 = [&] (int x)
	{
		return std::min(x, numSections - x);
	};
	
	//auto mid = std::lower_bound(p, p + numTeams, numSections / 2);
	int num0 = 0;
	int numL = 0;
	int numR = 0;
	for (int i = 0; i < numTeams; i++)
	{
		if (p[i] == 0)
			num0++;
		else if (p[i] * 2 < numSections)
			numL++;
		else
			numR++;
	}
	
	p += num0;
	numTeams -= num0;
	
	int doneL = 0;
	int doneR = 0;
	
	long long sec = 0;
	
	while ((doneL + doneR) < numTeams)
	{
		int boxes = capacity;
		
		auto Give = [&](int x, int numToGive)
		{
			if (x < numSections)
				numL -= numToGive;
			else
				numR -= numToGive;
			boxes -= numToGive;
		};
		
		if (numL > numR)
		{
			sec += DistTo0(p[doneL]);
			
			while (true)
			{
				int oldPos = p[doneL];
				
				int numToGive = 0;
				while (numToGive < boxes && p[doneL + numToGive] == oldPos)
					numToGive++;
				
				Give(oldPos, numToGive);
				doneL += numToGive;
				
				int nextDist = std::abs(p[doneL] - oldPos);
				int nextD0 = DistTo0(p[doneL]);
				int oldD0 = DistTo0(oldPos);
				
				if (boxes <= 0 || (doneL + doneR) >= numTeams || nextD0 + oldD0 < nextDist)
				{
					sec += oldD0;
					break;
				}
				
				sec += nextDist;
			}
		}
		else
		{
			sec += DistTo0(p[numTeams - doneR - 1]);
			
			while (true)
			{
				int oldPos = p[numTeams - doneR - 1];
				
				int numToGive = 0;
				while (numToGive < boxes && p[numTeams - doneR - numToGive - 1] == oldPos)
					numToGive++;
				
				Give(oldPos, numToGive);
				doneR += numToGive;
				
				int nextDist = std::abs(p[numTeams - doneR - 1] - oldPos);
				int nextD0 = DistTo0(p[numTeams - doneR - 1]);
				int oldD0 = DistTo0(oldPos);
				
				if (boxes <= 0 || (doneL + doneR) >= numTeams || nextD0 + oldD0 < nextDist)
				{
					sec += oldD0;
					break;
				}
				
				sec += nextDist;
			}
		}
	}
	
	return sec;
}

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