#include "robots.h"
#include <algorithm>
#include <vector>
#include <queue>
struct Item
{
Item(int l, int o, int c) : limit(l), othLim(o), carrying(c) {}
int limit, othLim, carrying;
bool operator <(const Item &other) const
{
return (other.carrying < carrying);
}
};
const int MAXN = 1e6;
const int MAXA = 5e4;
int weight[MAXN], size[MAXN];
int weightLimit[MAXA];
int sizeLimit[MAXA];
std::vector<Item> toSort;
std::priority_queue<Item> sorting;
std::vector<Item> given[MAXA];
std::vector<Item> unsorted;
bool cmplimit(const Item &a, const Item &b)
{
if (a.limit != b.limit)
return (a.limit > b.limit);
return (a.carrying < b.carrying);
}
bool cansolve(int time, int toys, int weak, int small)
{
toSort.clear();
while (!sorting.empty())
sorting.pop();
for (const Item &toy : unsorted)
toSort.emplace_back(toy);
for (int iRob = 0; iRob < weak; iRob++)
for (int iToy = given[iRob].size() - 1; iToy >= time; iToy--)
toSort.emplace_back(given[iRob][iToy]);
for (int iRob = 0; iRob < small; iRob++)
toSort.emplace_back(sizeLimit[iRob], iRob, 0);
std::sort(toSort.begin(), toSort.end(), cmplimit);
if (toSort.front().carrying == -1)
return false;
int maxTime = 0;
for (const Item &item : toSort)
{
if (item.carrying == 0)
sorting.emplace(item);
else
{
Item robot = sorting.top();
sorting.pop();
maxTime = std::max(maxTime, robot.carrying + 1);
sorting.emplace(robot.limit, robot.othLim, robot.carrying + 1);
}
}
return (maxTime <= time);
}
int searchans(int left, int right, int toys, int weak, int small)
{
if (left == right)
return toys + 1;
int time = (left + right) / 2;
if (cansolve(time, toys, weak, small))
return std::min(time, searchans(left, time, toys, weak, small));
return searchans(time + 1, right, toys, weak, small);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
int weak = A, small = B, toys = T;
for (int iRob = 0; iRob < weak; iRob++)
weightLimit[iRob] = X[iRob];
for (int iRob = 0; iRob < B; iRob++)
sizeLimit[iRob] = Y[iRob];
for (int iToy = 0; iToy < toys; iToy++)
{
weight[iToy] = W[iToy];
size[iToy] = S[iToy];
}
for (int iRob = 0; iRob < weak; iRob++)
toSort.emplace_back(weightLimit[iRob], iRob, 0);
for (int iToy = 0; iToy < toys; iToy++)
toSort.emplace_back(weight[iToy], size[iToy], -1);
std::sort(toSort.begin(), toSort.end(), cmplimit);
for (const Item &item : toSort)
{
if (item.carrying == 0)
sorting.emplace(item);
else if (sorting.empty())
unsorted.emplace_back(item.othLim, item.limit, -1);
else
{
Item robot = sorting.top();
sorting.pop();
given[robot.othLim].emplace_back(item.othLim, item.limit, -1);
sorting.emplace(robot.limit, robot.othLim, robot.carrying + 1);
}
}
for (int iRob = 0; iRob < weak; iRob++)
std::sort(given[iRob].begin(), given[iRob].end(), cmplimit);
int minTime = searchans(1, toys + 1, toys, weak, small);
if (minTime == toys + 1)
return -1;
else
return minTime;
return 0;
}
