Submission #333017

#	Time	Username	Problem	Language	Result	Execution time	Memory
333017		Cantfindme	Robots (IOI13_robots)	C++17	90 / 100	1775 ms	24136 KiB

robots

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#include "robots.h"
vector <pi> toys;
int n;
int weak[50010];
int small[50010];
int now,nos;

int query(int x) {
	priority_queue <int> pq;
	int cur = 0;
	for (int i = 0;i<now;i++) {
		while (cur < n and toys[cur].f < weak[i]) {
			cur++;
			pq.push(toys[cur].s);
		}
		for (int xd = 0; xd < x; xd++) {
			if (pq.empty()) break;
			pq.pop();
		}
	}
	while (cur < n) {
		pq.push(toys[cur].s);
		cur++;
	}
	for (int i = nos-1;i>=0;i--) {
		if (pq.empty()) return 1;
		else if (pq.top() >= small[i]) return 0;
		for (int xd = 0; xd < x; xd++) {
			if (pq.empty() or pq.top() >= small[i]) break;
			pq.pop();
		}
	}
	if (pq.empty()) return 1;
	else return 0;
}


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	n = T; now = A; nos = B;
	for (int i =0;i<A;i++) weak[i] = X[i];
	for (int i =0;i<B;i++) small[i] = Y[i];
	sort(weak,weak+A);
	sort(small,small+B);

	for (int i =0;i<n;i++) {
		toys.push_back(pi(W[i],S[i]));
	}
	sort(toys.begin(),toys.end());
	
	int high = T+1;
	int low = 0;
	while (high - low > 1) {
		
		int mid = (high+low)/2;
		//cout << low << " " << mid << " " << high << "\n";
		if (query(mid)) high = mid;
		else low = mid;
	}
	if (high == T+1) return -1;
	else return high;
}

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