Submission #62859

#	Time	Username	Problem	Language	Result	Execution time	Memory
62859		mhnd	Robots (IOI13_robots)	C++14	76 / 100	3034 ms	26016 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){
	int cur = 0;
	int rem = t;
	priority_queue<pair<int,int>> q;
	for(int i=0;i<a;i++){
		int cnt=md;
		while(cur<t && (vis[toy1[cur].second] || x[i] > toy1[cur].first.first)){
			if(!vis[toy1[cur].second])
				q.push({toy1[cur].first.second,toy1[cur].second});
			cur++;
		}
		while(q.size() && cnt--){
			int cur = q.top().second;
			q.pop();
			vis[cur]=1;
			rem--;
		}
	}
	q = priority_queue<pair<int,int>>();
	cur = 0;
	for(int i=0;i<b;i++){
		int cnt=md;
		while(cur<t && (vis[toy2[cur].second] || y[i] > toy2[cur].first.second)){
			if(!vis[toy2[cur].second])
				q.push({toy2[cur].first.first,toy2[cur].second});
			cur++;
		}
		while(q.size() && cnt--){
			int cur = q.top().second;
			q.pop();
			vis[cur]=1;
			rem--;
		}
	}
	return rem == 0;
}

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;
		memset(vis,0,sizeof(vis));
	}
    return ans;
}

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