Submission #1025573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025573		dozer	Robots (IOI13_robots)	C++14	100 / 100	1390 ms	18816 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int,int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define mid (l + r) / 2
#define ll long long
#define MAXN 200005
#define LOGN 19


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	vector<pii> v;
	for (int i = 0; i < T; i++)
		v.pb({W[i], S[i]});
	sort(v.begin(), v.end());

	sort(X, X + A);
	sort(Y, Y + B);

	auto check = [&](int val){
		priority_queue<int> q;
		int it = 0;
		for (int i = 0; i < A; i++){
			while(it < T && v[it].st < X[i]){
				q.push(v[it].nd);
				it++;
			}

			int sz = val;
			while(!q.empty() && sz > 0){
				q.pop();
				sz--;
			} 
		}

		while(it < T) q.push(v[it].nd), it++;

		for (int i = B - 1; i >= 0; i--){
			int sz = val;
			while(sz > 0 && !q.empty()){
				if (q.top() >= Y[i]) return 0;
				q.pop();
				sz--;
			}
		}

		if (!q.empty()) return 0;
		return 1;
	};


	int ans = 0;
	for (int i = LOGN; i >= 0; i--){
		int tmp = ans + (1<<i);
		if (check(tmp) == 0) ans = tmp;
	}

	ans++;
	if (check(ans) == 0) return -1;

	return ans;
}

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