제출 #125404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125404		MoNsTeR_CuBe	로봇 (IOI13_robots)	C++17	76 / 100	693 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[]) {
    
    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;
}
/*
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int a, b, t;
	cin >> a >> b >> t;
	
	int X[a], Y[b], W[t], S[t];
	
	for(int i = 0; i < a; i++){
		cin >> X[i];
	}
	for(int i = 0; i < b; i++){
		cin >> Y[i];
	}
	for(int i = 0; i < t; i++){
		cin >> W[i];
	}
	for(int i = 0; i < t; i++){
		cin >> S[i];
	}
	cout << putaway(a,b,t,X,Y,W,S) << endl;
}*/

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