Submission #706823

#	Time	Username	Problem	Language	Result	Execution time	Memory
706823		Doncho_Bonboncho	Robots (IOI13_robots)	C++14	100 / 100	1615 ms	24880 KiB

robots

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

const int MAX_N = 1e6 + 42;

std::pair<int, int> toys[MAX_N];
int small[MAX_N];
int weak[MAX_N];

int a, b, t;

bool f( int x ){
//	std::cerr<<" ! "<<x<<"\n";
	std::priority_queue<int> q;
	int ind = -1;
	for( int i=0 ; i<a ; i++ ){
		while( ind+1 < t and toys[ind+1].first < weak[i] ){
			q.push(toys[ind+1].second);
			ind++;
		}
		int num = x;
		while( !q.empty() and num ){
			num--;
			q.pop();
		}
	}
//	std::cerr<<" 1\n";
	while( ind+1 < t ){
		q.push( toys[ind+1].second );
		ind++;
	}
//	std::cerr<<"2\n";

	for( int i = b-1 ; i>=0 ; i-- ){
		if( q.empty() ) return true;
		int num = x;
		while( !q.empty() and num ){
			if( q.top() >= small[i] ) return false;
			q.pop();
			num--;
		}
	}

	return q.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	
	a = A;
	b = B;
	t = T;

	for( int i=0 ; i<a;  i++ ) weak[i] = X[i];
	for( int i=0 ; i<b;  i++ ) small[i] = Y[i];

	for( int i=0 ; i<t ; i++ ) toys[i] = {W[i], S[i]};
	
	std::sort( weak, weak + a );
	std::sort( small, small + b );
	std::sort( toys, toys + t );

	int l = 0, r = t;
	while( l < r-1 ){
		int m = ( l + r ) >> 1;
		if( f( m ) ) r = m;
		else l = m;
	}

	if( !f(r) ) return -1;
	return r;
}

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