#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;
};
//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)
{
// cerr << lo << ' ' << hi << '\n';
int lim = (lo+hi)/2;
vi unused;
vi nxt(A+1);
for(int a = 0; a < A; a++)
nxt[a] = a+1;
nxt[A] = A;
vi Acurr(A+1, 0);
// cerr << "A = " << A << '\n';
for(auto& t : toys)
{
int ws = worst_small[t.i];
while(Acurr[nxt[ws]] == lim)
{
// cerr << nxt[ws] << ' ' << Acurr[nxt[ws]] << '\n';
nxt[ws] = nxt[nxt[ws]];
}
if(Acurr[ws] == lim)
ws = nxt[ws];
if(ws == A)
unused.push_back(t.s);
else
{
Acurr[ws]++;
}
}
// cerr << "done\n";
vi Bcurr(B+1, 0);
int bi = 0;
bool works = 1;
for(int k : unused)
{
if(Bcurr[bi] == lim) bi++;
if(bi == B)
{
works = 0;
break;
}
while(bi < B && Y[bi] <= k)
bi++;
if(bi == B)
{
works = 0;
break;
}
Bcurr[bi]++;
}
if(works)
hi = lim;
else
lo = lim+1;
}
if(lo == T+1) return -1;
else return lo;
}
