#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X+A);
sort(Y, Y+B);
for(int i=0;i<A;i++)X[i]--;
for(int i=0;i<B;i++)Y[i]--;
vector<vector<int>> x(A), y(B);
for(int i=0;i<T;i++){
int tx=lower_bound(X, X+A, W[i])-X;
if(tx < A){
x[tx].push_back(i);
//~ printf("%d %d going to %d\n", W[i], S[i],tx);
}
//~ else printf("not in %d %d\n",W[i],S[i]);
if(W[i]>X[A-1] and S[i]>Y[B-1])return -1;
}
for(int i=0;i<T;i++){
int ty=lower_bound(Y,Y+B,S[i])-Y;
if(ty < B)y[ty].push_back(i);
}
for(int i=0;i<A;i++){
sort(x[i].begin(),x[i].end(),[&](int a, int b){
return S[a] < S[b];
});
}
for(int i=0;i<B;i++){
sort(y[i].begin(),y[i].end(),[&](int a,int b){
return W[a] < W[b];
});
}
int cnt=0;
vector<bool> done(T, 0);
vector<int> xp(A), yp(B);
for(int i=0;i<A;i++)xp[i]=i;
for(int i=0;i<B;i++)yp[i]=i;
auto par = [&](auto par, int c, vector<int> & p) -> int {
//~ cout<<c<<endl;
if(p[c]==c)return c;
return p[c]=par(par, p[c], p);
};
auto merge = [&](int a, int b, vector<int> & p) {
if(a < 0 or b<0)return;
int pa=par(par, a, p), pb=par(par, b, p);
if(pa==pb)return;
if(pa > pb) swap(pa, pb);
p[pb]=pa;
};
int itr=0;
while(cnt < T){
for(int i=A-1;i>=0;i--){
int cp=par(par, i, xp);
while(cp >= 0){
while (!x[cp].empty() && done[x[cp].back()])
x[cp].pop_back();
if(!x[cp].empty()){
done[x[cp].back()]=true;
cnt++;
//~ printf("x %d takes position %d %d\n", i,W[x[cp].back()], S[x[cp].back()]);
break;
}
else{
merge(cp, cp-1, xp);
if(cp==0)break;
}
cp=par(par, i, xp);
}
//~ printf("itr %d, i %d, cp %d\n", itr, i, cp);
//~ assert(ptr < A);
}
for(int i=B-1;i>=0;i--){
int cp=par(par, i, yp);
while(cp >= 0){
while(!y[cp].empty() and (done[y[cp].back()]))y[cp].pop_back();
if(!y[cp].empty()){
done[y[cp].back()]=true;
cnt++;
break;
}
else {
merge(cp, cp-1, yp);
if(cp==0)break;
}
cp=par(par, i, yp);
}
}
//~ for(int i=0;i<T;i++)cout<<done[i]<<" ";
//~ cout<<endl;
itr++;
//~ if(itr > 4)break;
}
return itr;
}
