Submission #60713

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60713	2018-07-24T15:04:14 Z	Eae02	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	2 ms	424 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 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	424 KB	Output is correct
5	Correct	2 ms	252 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	276 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	380 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	256 KB	Output is correct
5	Incorrect	2 ms	256 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 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	256 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 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	424 KB	Output is correct
5	Correct	2 ms	252 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	276 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Incorrect	2 ms	256 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 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	424 KB	Output is correct
5	Correct	2 ms	252 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	276 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Incorrect	2 ms	256 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 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	424 KB	Output is correct
5	Correct	2 ms	252 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	276 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Incorrect	2 ms	256 KB	Output isn't correct
13	Halted	0 ms	0 KB	-