제출 #125415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125415		MoNsTeR_CuBe	로봇 (IOI13_robots)	C++17	90 / 100	664 ms	65540 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

bool comp(vector< int > &A, vector< int > &B){
	return A.size() < B.size();
}

vector< int > used;

bool comp1(int a, int b){
	return used[a] < used[b];
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    
    if(B == 0){
		sort(X,X+A);
		sort(W,W+T);
		
		for(int i = 0; i < T; i++){
			if(W[i] >= X[A-1]) return -1;
		}
		
		int left = 1, right = T;
		
		while(left < right){
			
			int mid = (left+right)/2;
			
			int curr = 0;
			
			for(int i = 0; i < A; i++){
				int index = min((long)curr + mid, lower_bound(W+curr, W+T, X[i])-W);
			
				curr = index;
			}
			
			if(curr >= T){
				right = mid;
			}else{
				left = mid+1;
			}
		}
		
		return right;
	}
    
    vector< int > taken(T, false);
    
    vector< vector< int > > canTake(A+B);
    
    used.assign(T,0);
    
    for(int i = 0; i < A; i++){
		for(int j = 0; j < T; j++){
			if(W[j] < X[i]){
				canTake[i].push_back(j);
				used[j]++;
			} 
		}
	}
	
	for(int i = 0; i < B; i++){
		for(int j = 0; j < T; j++){
			if(S[j] < Y[i]){
				canTake[A+i].push_back(j);
				used[j]++;
			} 
		}
	}
	
	for(int i = 0; i < T; i++){
		if(used[i] <= 0){
			return -1;
		}
	}
    
    sort(canTake.begin(), canTake.end(), comp);
    
    for(int i = 0; i < A+B; i++){
		sort(canTake[i].begin(), canTake[i].end(),comp1);
	}
    
    int left = 1, right = T;
    
    while(left < right){
		int mid = (left+right)/2;
		
		for(int i = 0; i < A+B; i++){
			int tot = 0;
			
			for(int a : canTake[i]){
				if(taken[a]) continue;
				if(tot >= mid) break;
				tot ++;
				taken[a] = true;
			}
		}
		
		bool verif = true;
		
		for(int i = 0; i < T; i++){
			if(!taken[i]) verif = false;
		}
		
		if(!verif){
			left = mid+1;
		}else{
			right = mid;
		}
		
		fill(taken.begin(), taken.end(), false);
	}
    
    return right;
}

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