Submission #60713

#	Time	Username	Problem	Language	Result	Execution time	Memory
60713		Eae02	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	2 ms	424 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 numL = mid - p;
	int numR = numTeams - numL;
	
	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;
				
				if (boxes <= 0 || (doneL + doneR) >= numTeams)
				{
					sec += DistTo0(oldPos);
					break;
				}
				
				sec += std::abs(p[doneL] - oldPos);
			}
		}
		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;
				
				if (boxes <= 0 || (doneL + doneR) >= numTeams)
				{
					sec += DistTo0(oldPos);
					break;
				}
				
				sec += std::abs(p[numTeams - doneR - 1] - oldPos);
			}
		}
	}
	
	return sec;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:16:17: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  int numL = mid - p;
             ~~~~^~~

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