제출 #169536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169536		Lawliet	Robots (IOI13_robots)	C++17	90 / 100	3041 ms	51464 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 szLimit[MAXN];
int weightLimit[MAXN];

bool picked[MAXN];

vector< pii > sweepX;
vector< pii > sweepY;

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 test(int k)
{
	int p = 0;

	set< pii > s;

	vector< int > aux;

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

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

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

			int ind = s.begin()->second;
			picked[ ind ] = true;

			s.erase( s.begin() );
		}
	}

	p = 0;

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

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

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

			picked[ aux.back() ] = true;
			aux.pop_back();
		}
	}

	for(int i = 1 ; i <= N ; i++)
		if( !picked[i] ) return false;

	return true;
}

int bs()
{
	int l = 0;
	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.push_back( { sz[i] , i } );
		sweepY.push_back( { weight[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.begin() , sweepX.end() , cmp );
	sort( sweepY.begin() , sweepY.end() , cmp );
	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: 0 / 10