Submission #62852

#	Time	Username	Problem	Language	Result	Execution time	Memory
62852		mhnd	Robots (IOI13_robots)	C++14	53 / 100	652 ms	66560 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> toy1[1000010],toy2[1000010];
bool vis[1000010];

bool cmp1(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
    return a.first.first < b.first.first || (a.first.first == b.first.first && a.first.second < b.first.second);
}
bool cmp2(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
    return a.first.second < b.first.second || (a.first.second == b.first.second && a.first.first < b.first.first);
}

bool check(int md){
	for(int i=0;i<t;i++)vis[i]=0;
	int cur = t-1;
	for(int i=a-1;i>=0;i--){
		int cnt=0;
		while(cur>=0 && cnt < md){
			if(!vis[toy1[cur].second] && x[i] > toy1[cur].first.first){
				vis[toy1[cur].second] = 1;
				cnt++;
			}
			cur--;
		}
	}
	cur = t-1;
	for(int i=b-1;i>=0;i--){
		int cnt=0;
		while(cur>=0 && cnt < md){
			if(!vis[toy2[cur].second] && y[i] > toy2[cur].first.second){
				vis[toy2[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++)toy1[i] = toy2[i] = {{W[i],S[i]},i};
	sort(toy1, toy1 + t, cmp1);
    sort(toy2, toy2 + t, cmp2);
	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: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10