Submission #169538

#	Time	Username	Problem	Language	Result	Execution time	Memory
169538		Lawliet	Robots (IOI13_robots)	C++14	100 / 100	2706 ms	33900 KiB

robots

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

using namespace std;
typedef pair<int,int> pii;

const int MAXN = 1000010;

int N;
int qtdWeak;
int qtdSmall;

int sz[MAXN];
int weight[MAXN];
int sweepX[MAXN];
int sweepY[MAXN];
int szLimit[MAXN];
int weightLimit[MAXN];

bool picked[MAXN];

bool cmp(pii a, pii b)
{
	int indA = a.second;
	int indB = b.second;

	if( a.first != b.first ) return a.first < b.first;
	return weight[indA] + sz[indA] < weight[indB] + sz[indB];
}

bool cmpSz(int i, int j) { return sz[i] < sz[j]; }
bool cmpWeight(int i, int j) { return weight[i] < weight[j]; }

bool test(int k)
{
	int p = 1;
	int qtdToys = 0;

	vector< int > aux;
	priority_queue< pii > s;

	memset( picked , false , sizeof(picked) );

	for(int i = 1 ; i <= qtdSmall ; i++)
	{
		while( p <= N && sz[ sweepX[p] ] < szLimit[i] )
		{
			int ind = sweepX[ p++ ];
			s.push( { weight[ind] , ind } );
		}

		for(int j = 0 ; j < k ; j++)
		{
			if( s.empty() ) break;

			int ind = s.top().second;

			qtdToys++;
			picked[ ind ] = true;

			s.pop();
		}
	}

	p = 1;

	for(int i = 1 ; i <= qtdWeak ; i++)
	{
		while( p <= N && weight[ sweepY[p] ] < weightLimit[i] )
		{
			int ind = sweepY[ p++ ];

			if( picked[ind] ) continue;
			aux.push_back( ind );
		}

		for(int j = 0 ; j < k ; j++)
		{
			if( aux.empty() ) break;

			qtdToys++;
			picked[ aux.back() ] = true;

			aux.pop_back();
		}
	}

	return qtdToys == N;
}

int bs()
{
	int l = 1;
	int r = N;

	if( !test( r ) ) return -1;

	while( l < r )
	{
		int m = ( l + r )/2;

		if( test( m ) ) r = m;
		else l = m + 1;
	}

	return r;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) 
{
	N = T;
	qtdWeak = A;
	qtdSmall = B;

	for(int i = 1 ; i <= N ; i++)
	{
		sz[i] = S[i - 1];
		weight[i] = W[i - 1];

		sweepX[i] = sweepY[i] = i;
	}

	for(int i = 1 ; i <= qtdWeak ; i++)
		weightLimit[i] = X[i - 1];

	for(int i = 1 ; i <= qtdSmall ; i++)
		szLimit[i] = Y[i - 1];

	sort( sweepX + 1 , sweepX + N + 1 , cmpSz );
	sort( sweepY + 1 , sweepY + N + 1  , cmpWeight );

	sort( szLimit + 1 , szLimit + qtdSmall + 1 );
	sort( weightLimit + 1 , weightLimit + qtdWeak + 1 );

    return bs();
}

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