Submission #384116

#	Time	Username	Problem	Language	Result	Execution time	Memory
384116		alishahali1382	Robots (IOI13_robots)	C++14	100 / 100	2011 ms	45024 KiB

robots

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

using namespace std;

typedef pair<int, int> pii;
#define pb push_back
#define all(x) x.begin(), x.end()

const int MAXN=1000010;

int n, m, T;
int X[MAXN], Y[MAXN], A[MAXN], B[MAXN];
vector<int> vec[MAXN], compx, compy;
priority_queue<pii> pq;

bool Check(int k){
	while (pq.size()) pq.pop();
	for (int i=0; i<=n; i++){
		for (int j:vec[i]) pq.push({B[j], j});
		if (i<n){
			int t=min((int)pq.size(), k);
			while (t--) pq.pop();
		}
	}
	for (int i=m-1; ~i; i--){
		int t=min((int)pq.size(), k);
		while (t--){
			if (pq.top().first>=Y[i]) break ;
			pq.pop();
		}
	}
	return pq.empty();
}

int putaway(int nn, int mm, int TT, int XX[], int YY[], int WW[], int SS[]){
	n=nn;
	m=mm;
	T=TT;
	for (int i=0; i<n; i++) X[i]=XX[i];
	for (int i=0; i<m; i++) Y[i]=YY[i];
	sort(X, X+n);
	sort(Y, Y+m);

	for (int i=0; i<T; i++){
		int x=WW[i], y=SS[i];
		A[i]=upper_bound(X, X+n, x)-X;
		// B[i]=upper_bound(Y, Y+m, y)-Y;
		B[i]=y;
		vec[A[i]].pb(i);
	}
	int dwn=0, up=T+1;
	while (up-dwn>1){
		int mid=(dwn+up)>>1;
		if (Check(mid)) up=mid;
		else dwn=mid;
	}
	if (up==T+1) return -1;
	return up;
}

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