Submission #891695

#	Time	Username	Problem	Language	Result	Execution time	Memory
891695		AgentPengin	Robots (IOI13_robots)	C++14	100 / 100	1408 ms	40044 KiB

robots

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>
#include"robots.h"


#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 5e4 + 10;
const int MAXS = 1e6 + 5;

pair<ll,ll> toys[MAXS];
ll r1[MAXN],r2[MAXN];
vector<ll> pre[MAXN];
ll n,m,t;

bool check(ll k) {
	priority_queue<ll> pq;
	for (int i = 1;i <= n;i++) {
		for (auto x : pre[i]) {
			pq.push(x);
		}
		ll cur = 0;
		while(!pq.empty() && cur < k) {
			pq.pop();
			++cur;
		}
	}
	for (auto x : pre[n + 1]) pq.push(x);
	for (int i = m;i >= 1;i--) {
		ll cnt = 0;
		while(!pq.empty() && cnt < k) {
			if (pq.top() >= r2[i]) return 0;
			pq.pop();
			++cnt;
		}
	}
	return pq.empty();
}

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]) {
	n = A,m = B;
	t = T;
	for (ll i = 1;i <= n;i++) {
		r1[i] = X[i - 1];
	}
	for (ll i = 1;i <= m;i++) {
		r2[i] = Y[i - 1];
	}
	sort(r1 + 1,r1 + n + 1);
	sort(r2 + 1,r2 + m + 1);
	r1[n + 1] = 1e18;
	for (int i = 1;i <= t;i++) {
		toys[i].fi = W[i - 1];
		toys[i].se = S[i - 1];
	}
	sort(toys + 1,toys + t + 1);
	ll cur = 1;
	for (int i = 1;i <= t;i++) {
		while(r1[cur] <= toys[i].fi) ++cur;
		pre[cur].push_back(toys[i].se);
	}
	ll l = 0,r = t + 1;
	while((l + 1) < r) {
		ll mid = (l + r) / 2;
		if (check(mid)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	if (check(r)) return r;
	else return -1;
	
}

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