Submission #931497

#	Time	Username	Problem	Language	Result	Execution time	Memory
931497		OAleksa	Robots (IOI13_robots)	C++14	100 / 100	1705 ms	38448 KiB

robots

#include <bits/stdc++.h>
#include"robots.h"
using namespace std;
#define f first
#define s second

int putaway(int A, int B, int t, int x[], int y[], int w[], int s[]) {
  int n = A, m = B;
  sort(x, x + n);
  sort(y, y + m);
  for (int i = 0;i < t;i++) {
  	if (w[i] >= x[n - 1] && s[i] >= y[m - 1]) 
  		return -1;
  }
  vector<tuple<int, int, int>> a, b;
  for (int i = 0;i < t;i++) {
  	a.push_back({w[i], s[i], i});
  	b.push_back({s[i], w[i], i});
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
 	int l = 1, r = t, ans = t;
 	vector<int> vis(t);
 	auto check = [&](int mid) {
 		for (int i = 0;i < t;i++)
 			vis[i] = 0;
 		int ptr = 0;
 		priority_queue<pair<int, int>> pq;
 		for (int i = 0;i < n;i++) {
 			while (ptr < t && get<0>(a[ptr]) < x[i]) {
 				if (!vis[get<2>(a[ptr])])
 					pq.push({get<1>(a[ptr]), get<2>(a[ptr])});
 				ptr++;
 			}
 			for (int j = 0;j < mid;j++) {
 				if (pq.empty())
 					break;
 				auto u = pq.top();
 				vis[u.s] = 1;
 				pq.pop();
 			}
 		}
 		while (!pq.empty())
 			pq.pop();
 		ptr = 0;
 		for (int i = 0;i < m;i++) {
 			while (ptr < t && get<0>(b[ptr]) < y[i]) {
 				if (!vis[get<2>(b[ptr])])
 					pq.push({get<1>(b[ptr]), get<2>(b[ptr])});
 				ptr++;
 			}
 			for (int j = 0;j < mid;j++) {
 				if (pq.empty())
 					break;
 				auto u = pq.top();
 				vis[u.s] = 1;
 				pq.pop();
 			}
 		}
 		int g = 1;
 		for (int i = 0;i < t;i++)
 			g &= vis[i];
 		return g;
 	};
 	while (l <= r) {
 		int mid = (l + r) / 2;
 		if (check(mid)) {
 			ans = mid;
 			r = mid - 1;
 		}
 		else
 			l = mid + 1;
 	}
 	return ans;
}                                                                                                             

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