Submission #59271

#	Time	Username	Problem	Language	Result	Execution time	Memory
59271		TadijaSebez	Robots (IOI13_robots)	C++11	100 / 100	2484 ms	57328 KiB

robots

#include "robots.h"
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
const int N=1000050;
const int M=50050;
int x[M],y[M];
pair<int,int> toy[N];
bool Check(int n, int a, int b, int mid)
{
	priority_queue<int> pq;
	int i,j=1,k;
	for(i=1;i<=a;i++)
	{
		while(j<=n && toy[j].first<=x[i]) pq.push(toy[j].second),j++;
		for(k=1;k<=mid;k++)
		{
			if(pq.empty()) break;
			pq.pop();
		}
	}
	while(j<=n) pq.push(toy[j].second),j++;
	for(i=b;i>=1;i--)
	{
		for(k=1;k<=mid;k++)
		{
			if(pq.empty()) return 1;
			if(pq.top()>y[i]) return 0;
			pq.pop();
		}
	}
	return pq.empty();
}
int putaway(int a, int b, int n, int X[], int Y[], int W[], int S[])
{
	int i;
	for(i=1;i<=n;i++) toy[i]=mp(W[i-1]+1,S[i-1]+1);
	sort(toy+1,toy+1+n);
	for(i=1;i<=a;i++) x[i]=X[i-1];
	sort(x+1,x+1+a);
	for(i=1;i<=b;i++) y[i]=Y[i-1];
	sort(y+1,y+1+b);
	int top=n,bot=1,mid,ans=-1;
	while(top>=bot)
	{
		mid=top+bot>>1;
		if(Check(n,a,b,mid)) ans=mid,top=mid-1;
		else bot=mid+1;
	}
	return ans;
}
//---------------------//
/*
int X[M],Y[M],W[N],S[N];
int main()
{
	int n,a,b,i;
	scanf("%i %i %i",&a,&b,&n);
	for(i=0;i<a;i++) scanf("%i",&X[i]);
	for(i=0;i<b;i++) scanf("%i",&Y[i]);
	for(i=0;i<n;i++) scanf("%i %i",&W[i],&S[i]);
	printf("%i\n",putaway(a,b,n,X,Y,W,S));
	return 0;
}
*/
//---------------------//

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:49:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~

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