Submission #1007523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007523		pawned	Robots (IOI13_robots)	C++17	100 / 100	2672 ms	65536 KiB

robots

// no pragmas here

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
 
#include "robots.h"
 
const int MAX_A = 5e4 + 5;
const int MAX_N = 1e6 + 5;
 
int N;  // number of toys
int A, B;   // count capped by weight, by size
 
vi X, Y;
 
vector<ii> toys;	// {size, weight}
multiset<int> allwf;	// all weights, create this multiset only once
 
bool check(int D) { // true if can clean in D days
//	cout<<"at "<<D<<endl;
	if ((ll)(D) * (ll)(A + B) < (ll)(N))
		return false;
	vi alls;	// all capped by size
	int ctr = 0;
	for (int i = B - 1; i >= 0; i--) {
		for (int j = 0; j < D; j++) {
			alls.pb(Y[i]);
			ctr++;
			if (ctr == N)
				break;
		}
		if (ctr == N)
			break;
	}
	reverse(alls.begin(), alls.end());
/*	cout<<"alls: ";
	for (int x : alls)
		cout<<x<<" ";
	cout<<endl;*/
	priority_queue<int, vector<int>> pq;	// existing weights
	// remove heaviest posssible
	multiset<int> allw = allwf;
	int idx = 0;	// next index to add
	for (int x : alls) {
//		cout<<"at "<<x<<endl;
		while (idx < N) {
			if (toys[idx].fi <= x) {
				pq.push(toys[idx].se);
				idx++;
			}
			else {
				break;
			}
		}
//		cout<<"working "<<pq.size()<<endl;
		// remove the heaviest
		if (!pq.empty()) {
			int x = pq.top();
			pq.pop();
//			cout<<"removing "<<x<<endl;
			allw.erase(allw.find(x));
		}
	}
	// check if majorizes
	vi remw;	// remaining weights
	for (int x : allw)
		remw.pb(x);
/*	cout<<"remw: ";
	for (int x : remw)
		cout<<x<<" ";
	cout<<endl;*/
	ctr = (int)(remw.size()) - 1;
	for (int i = A - 1; i >= 0; i--) {
		for (int j = 0; j < D; j++) {
			if (ctr == -1)
				break;
			if (X[i] < remw[ctr])
				return false;
			ctr--;
		}
		if (ctr == -1)
			break;
	}
	if (ctr != -1)
		return false;
	return true;
}
// if need to speed up, change multiset to priority queue (?)
 
int putaway(int a, int b, int t, int c[], int d[], int w[], int s[]) {
	A = a; B = b; N = t;
	sort(c, c + A);
	sort(d, d + B);
	for (int i = 0; i < A; i++) {
		X.pb(c[i] - 1);
	}
	for (int i = 0; i < B; i++) {
		Y.pb(d[i] - 1);
	}
	// sort toys by increasing size
	for (int i = 0; i < N; i++) {
		toys.pb({s[i], w[i]});
	}
	sort(toys.begin(), toys.end());
	for (ii p : toys)
		allwf.insert(p.se);
//	cout<<check(3)<<endl;
	int low = 0;
	int high = N;   // at most N minutes if possible
	int ans = -1;   // min number of days D to clean all
	while (low <= high) {   // false, false, false, true, true, true
		int mid = (low + high) / 2;
		if (check(mid)) {
			high = mid - 1;
			ans = mid;
		}
		else {
			low = mid + 1;
		}
	}
	return ans;
//	return 0;
}

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