/***********************************************
* auth: tapilyoca *
* date: 04/15/2025 at 12:28:45 *
* dots: https://github.com/tapilyoca/dotilyoca *
***********************************************/
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
const long long MOD = 1e9+7;
template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;
/***********************************************/
struct Toy {
int weight, size, index;
Toy(int a, int b, int c) : weight(0), size(0), index(0) {
weight = a;
size = b;
index = c;
}
};
bool byWeight(const Toy&one, const Toy&two) {
if(one.weight == two.weight) return one.size < two.size;
return one.weight < two.weight;
}
bool bySize(const Toy&one, const Toy&two) {
if(one.size == two.size) return one.weight < two.weight;
return one.size < two.size;
}
vector<Toy> toysByWeight;
vector<Toy> toysBySize;
vector<int> weak;
vector<int> small;
vector<bool> vis;
int a, b, t;
bool check(int tt) {
// returns true if possible to get t or less
// first assign weak
int assigned = 0;
int at = 0;
priority_queue<pair<int,int>> pq;
// greedy: from weakest to strongest, get everyone they can take and let them take the biggest among those
for(int i = 0; i < a; i++) {
while(at < t) {
// cerr << "i at " << i << " " << at << endl;
if(toysByWeight[at].weight >= weak[i]) break;
if(vis[toysByWeight[at].index]) {
at++;
continue;
}
pq.push({toysByWeight[at].size, toysByWeight[at].index});
at++;
}
int taken = 0;
while(!pq.empty() and taken != tt) {
int thingWeTake = pq.top().second;
pq.pop();
vis[thingWeTake] = 1;
taken++;
assigned++;
}
// dbg(assigned);
}
// cerr << "here" << endl;
priority_queue<pair<int,int>> pq2;
at = 0;
for(int i = 0; i < b; i++) {
while(at < t) {
// cerr << "i at " << i << " " << at << endl;
if(toysBySize[at].size >= small[i]) break;
if(vis[toysBySize[at].index]) {
at++;
continue;
}
// dbg(0);
pq2.push({toysBySize[at].weight, toysBySize[at].index});
at++;
}
int taken = 0;
while(!pq2.empty() and taken != tt) {
// cerr << "hello" << endl;
int thingWeTake = pq2.top().second;
pq2.pop();
vis[thingWeTake] = 1;
taken++;
assigned++;
}
}
if(assigned == t) {
return true;
} return false;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a = A;
b = B;
t = T;
for(int i = 0; i < A; i++) weak.pb(X[i]);
for(int i = 0; i < B; i++) small.pb(Y[i]);
for(int i = 0; i < T; i++) {
toysByWeight.pb(Toy(W[i],S[i],i));
toysBySize.pb(Toy(W[i],S[i],i));
}
sort(weak.begin(), weak.end());
sort(small.begin(), small.end());
sort(toysByWeight.begin(), toysByWeight.end(), byWeight);
sort(toysBySize.begin(), toysBySize.end(), bySize);
// for(int i = 0; i < t; i++) {
// cerr << toysByWeight[i].weight << " ";
// } cerr << endl;
// for(int i = 0; i < t; i++) {
// cerr << toysBySize[i].size << " ";
// } cerr << endl;
int lp = 1, rp = T;
while(lp <= rp) {
// cerr << lp << " " << rp << endl;
vis.assign(t,0);
int m = (lp+rp)>>1;
if(check(m)) {
// possible to get m or less so neglect right half
rp = m - 1;
} else {
lp = m + 1;
}
}
vis.assign(t,0);
if(check(lp)) return lp;
else return -1;
}
