Submission #125411

#	Time	Username	Problem	Language	Result	Execution time	Memory
125411		MoNsTeR_CuBe	Robots (IOI13_robots)	C++17	Compilation error	0 ms	0 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 > A){
				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;
}

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;
}

Compilation message (stderr)

/tmp/ccwxzm7h.o: In function `main':
robots.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccOrfBbe.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccOrfBbe.o: In function `main':
grader.c:(.text.startup+0x17e): undefined reference to `putaway'
collect2: error: ld returned 1 exit status