#include <bits/stdc++.h>
#include "robots.h"
#define all(v) v.begin(), v.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define sz(v) (int)v.size()
#define pb push_back
//#define int long long
using namespace std;
struct Chose
{
bool estRobot;
bool triTaille;
int taille, poids;
bool operator < (const Chose &autre) const
{
if (triTaille && taille != autre.taille)
return taille < autre.taille;
else if (!triTaille && poids != autre.poids)
return poids < autre.poids;
else if (estRobot != autre.estRobot)
return estRobot;
return false;
}
};
int nFragiles, nPetits;
int nJouets;
vector<Chose> jouets, robotsFragiles, robotsPetits;
vector<Chose> objets;
bool fonctionne (int limite){
priority_queue<Chose> jouetsPasRanges;
for (Chose& objet : objets){
if (objet.estRobot){
int nPris = 0;
while (!jouetsPasRanges.empty() && nPris < limite){
jouetsPasRanges.pop();
nPris++;
}
}
else {
objet.triTaille = true;
jouetsPasRanges.push(objet);
objet.triTaille = false;
}
}
//Il reste quelque truc qu'on va essayer de recup
vector<Chose> objetsn;
while (!jouetsPasRanges.empty()){
Chose jouet = jouetsPasRanges.top();
jouet.triTaille = true;
objetsn.pb(jouet);
jouetsPasRanges.pop();
}
reverse(all(objetsn));
//cout << limite << endl;
int pasRanges = 0, ptOb = 0, ptPetits = 0;
while (ptOb != sz(objetsn) || ptPetits != nPetits){
if (ptOb == sz(objetsn) || robotsPetits[ptPetits] < objetsn[ptOb])
pasRanges = max(pasRanges - limite, 0), ptPetits++;
else
pasRanges++, ptOb++;
}
return pasRanges == 0;
}
bool possible(){
int maxPoids = 0, maxTaille = 0;
for (Chose robot : robotsFragiles) chmax(maxPoids, robot.poids);
for (Chose robot : robotsPetits) chmax(maxTaille, robot.taille);
for (Chose jouet : jouets){
if (jouet.poids >= maxPoids && jouet.taille >= maxTaille)
return false;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
nFragiles = A;
nPetits = B;
nJouets = T;
robotsFragiles.resize(nFragiles);
robotsPetits.resize(nPetits);
jouets.resize(nJouets);
for (int ind = 0; ind < nFragiles; ++ind)
robotsFragiles[ind] = {true, false, -1, X[ind]};
for (int ind = 0; ind < nPetits; ++ind)
robotsPetits[ind] = {true, true, Y[ind], -1};
for (int ind = 0; ind < nJouets; ++ind)
jouets[ind] = {false, false, S[ind], W[ind]};
if (!possible())
return -1;
for (Chose& jouet : jouets){
jouet.triTaille = false;
objets.pb(jouet);
}
for (Chose& robotFragile : robotsFragiles)
objets.pb(robotFragile);
sort(all(objets));
sort(all(robotsPetits));
int deb = (nJouets)/(nFragiles + nPetits), fin = nJouets;
while (fin > deb){
int milieu = (deb + fin)/2;
if (fonctionne(milieu))
fin = milieu;
else
deb = milieu + 1;
}
return deb;
}
