#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]];
}
}
vi parent;
vi subtree;
vi lrg;
int root(int u)
{
if(u == parent[u]) return u;
else return (parent[u] = root(parent[u]));
}
void join(int u, int v)
{
u = root(u);
v = root(v);
if(u == v) return;
if(subtree[u] < subtree[v]) swap(u, v);
parent[v] = u;
subtree[u] += subtree[v];
lrg[u] = max(lrg[u], lrg[v]);
}
//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";
parent = subtree = lrg = vi(A+1);
int lo = 1, hi = T+1;
while(lo != hi)
{
int lim = (lo+hi)/2;
vi Acurr(1+A, 0);
vi unused;
for(int i = 0; i <= A; i++)
{
parent[i] = lrg[i] = i;
subtree[i] = 1;
}
for(auto& t : toys)
{
int wa = lrg[root(worst_small[t.i])];
if(wa == A)
unused.push_back(t.s);
else
{
Acurr[wa]++;
if(Acurr[wa] == lim)
join(wa, wa+1);
}
}
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;
}
