제출 #270501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270501		Mounir	로봇 (IOI13_robots)	C++14	0 / 100	1 ms	512 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;
	}
};
 
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;
}

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