Submission #270489

#	Time	Username	Problem	Language	Result	Execution time	Memory
270489		Mounir	Robots (IOI13_robots)	C++14	90 / 100	3093 ms	41532 KiB

robots

#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;
	}
	
	void dbg(){
		return;
		cout << estRobot << " " << triTaille << " " << taille << " " << poids << endl;
	}
};
 
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();
	}
	
	for (Chose& robotPetit : robotsPetits){
		robotPetit.triTaille = true;
		objetsn.pb(robotPetit);
	}
	
	sort(all(objetsn));
	
	int pasRanges = 0;
	//cout << "LMT " << limite << endl;
	for (Chose& objet : objetsn){
		if (objet.estRobot)
			pasRanges = max(pasRanges - limite, 0);
		else 
			pasRanges++;
	}
	
	return pasRanges == 0;
}
 
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]};
	
	for (Chose& jouet : jouets){
		jouet.triTaille = false;
		objets.pb(jouet);
	}
	for (Chose& robotFragile : robotsFragiles)
		objets.pb(robotFragile);
	
	sort(all(objets));
	
	int deb = (nJouets)/(nFragiles + nPetits), fin = nJouets + 5;
	while (fin > deb){
		int milieu = (deb + fin)/2;
		
		if (fonctionne(milieu))
			fin = milieu;
		else
			deb = milieu + 1;
	}
	
	if (deb > nJouets)
		return -1;
	return deb;
}
 

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10