Submission #62851

#	Time	Username	Problem	Language	Result	Execution time	Memory
62851		mhnd	Robots (IOI13_robots)	C++14	14 / 100	3058 ms	33424 KiB

robots

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 5e4+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

int a,b,t,x[N],y[N];
pair<pair<int,int>,int> toy[1000010];
bool vis[1000010];

bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
	if(a.first.second == b.first.second)return a.first.first > b.first.first;
	else return a.first.second > b.first.second;
}

bool check(int md){
	for(int i=0;i<t;i++)vis[i]=0;
	int cur = t-1;
	sort(toy,toy+t);
	for(int i=a-1;i>=0;i--){
		int cnt=0;
		while(cur>=0 && cnt < md){
			if(!vis[toy[cur].second] && x[i] > toy[cur].first.first){
				vis[toy[cur].second] = 1;
				cnt++;
			}
			cur--;
		}
	}
	sort(toy,toy+t,cmp);
	cur = t-1;
	for(int i=b-1;i>=0;i--){
		int cnt=0;
		while(cur>=0 && cnt < md){
			if(!vis[toy[cur].second] && y[i] > toy[cur].first.second){
				vis[toy[cur].second] = 1;
				cnt++;
			}
			cur--;
		}
	}
	for(int i=0;i<t;i++)if(!vis[i])return 0;
	return 1;
}

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++)x[i]=X[i];
	for(int i=0;i<b;i++)y[i]=Y[i];
	for(int i=0;i<t;i++)toy[i] = {{W[i],S[i]},i};
	sort(x,x+a);
	sort(y,y+b);
	int md,lo=0,hi=t,ans=-1;
	while(lo <= hi){
		md = (lo+hi)/2;
		if(check(md)){
			hi = md-1;
			ans = md;
		}else lo = md+1;
	}
    return ans;
}

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