#include "robots.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
struct toy
{
int w;
int s;
int i;
};
void recalibrate(int i, vi& nxt, vi& Acurr, int lim)
{
if(Acurr[nxt[i]] < lim) return;
else
{
recalibrate(nxt[i], nxt, Acurr, lim);
nxt[i] = nxt[nxt[i]];
}
}
//weak #, small #, toys #, weight lim, size lim, toy weight, toy size
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
// swap(A, B);
// swap(X, Y);
// swap(W, S);
sort(X, X+A);
sort(Y, Y+B);
vector<toy> toys(T);
// cerr << "done\n";
for(int t = 0; t < T; t++)
{
// cerr <<
toys[t] = {W[t], S[t], t};
// cerr << "done : " << t << '\n';
}
sort(toys.begin(), toys.end(), [] (toy u, toy v)
{
return u.w < v.w;
});
vi worst_small(T, A);
int it = -1;
for(int a = 0; a < A; a++)
{
while(it+1 < T && toys[it+1].w < X[a])
{
it++;
worst_small[toys[it].i] = a;
}
}
sort(toys.begin(), toys.end(), [] (toy u, toy v)
{
return u.s > v.s;
});
// cerr << "done\n";
int lo = 1, hi = T+1;
while(lo != hi)
{
int lim = (lo+hi)/2;
vi Acurr(1+A, 0);
vi unused;
for(auto& t : toys)
{
int wa = 0;
while(wa < A && (X[wa] <= t.w || Acurr[wa] == lim))
wa++;
if(wa == A)
unused.push_back(t.s);
else
Acurr[wa]++;
}
bool works = 1;
int wb = 0;
vi Bcurr(1+B, 0);
reverse(unused.begin(), unused.end());
for(int k : unused)
{
while(wb < B && (Y[wb] <= k || Bcurr[wb] == lim))
wb++;
if(wb == B)
works = 0;
else
Bcurr[wb]++;
}
if(works)
hi = lim;
else
lo = lim+1;
}
if(lo == T+1) return -1;
else return lo;
}
