Submission #768800

#	Time	Username	Problem	Language	Result	Execution time	Memory
768800		caganyanmaz	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	340 KiB

boxes

#include <bits/stdc++.h>
#define f first
#define s second
#define int int64_t
#ifdef DEBUGGING
#define debug(x) cout << (#x) << ": " << (x) << "\n";
#else
#define debug(x) 42
#endif
using namespace std;


map<int, int> mleft, mright;
int k, l;
int mid;

void safe_insert(map<int, int>& m, int val)
{
	if (m.find(val) == m.end())
		m[val] = 0;
	m[val]++;
}

int calculate_left_cost()
{
	int sum = 0, pr = 0;
	for (auto it = mleft.rbegin(); it != mleft.rend(); it++)
	{
		if (it->second > pr)
		{
			int val = it->second - pr;
			pr = val % k;
			int steps = val / k;
			if (pr != 0)
				steps++;
			sum += it->first * 2 * steps;
		}
		else
		{
			pr -= it->second;
		}
	}
	return sum;
}

int calculate_right_cost()
{
	int sum = 0, pr = 0;
	for (auto [pos, val] : mright)
	{
		if (val > pr)
		{
			val -= pr;
			pr = val % k;
			int steps = val / k;
			if (pr != 0)
				steps++;
			sum += (l-pos) * 2 * steps;
		}
		else
		{
			pr -= val;
		}
	}
	return sum;
}

int calculate_touring_cost(int val)
{
	int steps = val / k;
	if (val%k)
		steps++;
	return l * steps;
}


int delivery(int32_t N, int32_t K, int32_t L, int32_t p[])
{
	k = K, l = L;
	// Seperate parties
	int left_sum = 0, right_sum = 0;
	for (int i = 0; i < N; i++)
	{
		if (p[i] > L / 2)
		{
			safe_insert(mright, p[i]);
			right_sum++;
		}
		else if (p[i] < L / 2 && p[i] != 0)
		{
			left_sum++;
			safe_insert(mleft, p[i]);
		}
		else if (p[i] != 0)
		{
			mid++;
		}
	}
	int lr = left_sum % K, rr = right_sum % K;
	int lcr = calculate_left_cost(), rcr = calculate_right_cost();
	debug(lcr);
	debug(rcr);
	int leftover = lr;
	for (auto it = mleft.rbegin(); it != mleft.rend() && leftover > 0; it++)
	{
		int change = min(leftover, it->second);
		it->second -= change;
		leftover -= change;
	}
	leftover = rr;
	for (auto& [pos, val] : mright)
	{
		int change = min(leftover, val);
		val -= change;
		leftover -= change;
	}
	int lc = calculate_left_cost(), rc = calculate_right_cost();
	return min({
			lcr + rcr + calculate_touring_cost(mid),	
			lc  + rcr + calculate_touring_cost(mid + lr),
			lcr + rc  + calculate_touring_cost(mid + rr),
			lc  + rc  + calculate_touring_cost(mid + lr + rr)
		});
}

Compilation message (stderr)

boxes.cpp: In function 'int64_t delivery(int32_t, int32_t, int32_t, int32_t*)':
boxes.cpp:8:18: warning: statement has no effect [-Wunused-value]
    8 | #define debug(x) 42
      |                  ^~
boxes.cpp:101:2: note: in expansion of macro 'debug'
  101 |  debug(lcr);
      |  ^~~~~
boxes.cpp:8:18: warning: statement has no effect [-Wunused-value]
    8 | #define debug(x) 42
      |                  ^~
boxes.cpp:102:2: note: in expansion of macro 'debug'
  102 |  debug(rcr);
      |  ^~~~~

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