Submission #968633

#	Time	Username	Problem	Language	Result	Execution time	Memory
968633		mannshah1211	Robots (IOI13_robots)	C++17	100 / 100	1982 ms	29952 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
  vector<int> xs, ys;
  vector<pair<int, int>> books(t);
  for (int i = 0; i < a; i++) {
    xs.push_back(x[i]);
  }
  for (int i = 0; i < b; i++) {
    ys.push_back(y[i]);
  }
  for (int i = 0; i < t; i++) {
    books[i] = make_pair(w[i], s[i]);
  }
  sort(xs.begin(), xs.end());
  sort(ys.begin(), ys.end());
  int mxx = (xs.empty()) ? INT_MIN : xs.back(), mxy = (ys.empty()) ? INT_MIN : ys.back();
  for (int i = 0; i < t; i++) {
	if (w[i] >= mxx && s[i] >= mxy) {
	  return -1;
	}
  }
  vector<int> precalca(t, b), precalcb(t, a);
  sort(books.rbegin(), books.rend());
  for (int i = 0; i < t; i++) {
	int lowpos = upper_bound(ys.begin(), ys.end(), books[i].second) - ys.begin();
	precalca[i] = lowpos;
	int lowwpos = upper_bound(xs.begin(), xs.end(), books[i].first) - xs.begin();
	precalcb[i] = lowwpos;
  }
  auto ok = [&](int mid) {
	vector<int> acx(a), acy(b);
	set<int> not_full_indicesa, not_full_indicesb;
	for (int i = 0; i < a; i++) {
	  not_full_indicesa.insert(i);
	}
	for (int i = 0; i < b; i++) {
	  not_full_indicesb.insert(i);
	}
	vector<bool> ass(t);
	for (int i = 0; i < t; i++) {
	  auto it = not_full_indicesb.lower_bound(precalca[i]);
	  if (it != not_full_indicesb.end()) {
		int k = *it;
		++acy[k];
		if (acy[k] == mid) {
		  not_full_indicesb.erase(it);
		}
		ass[i] = true;
	  }
	}
	for (int i = 0; i < t; i++) {
	  if (!ass[i]) {
		auto it = not_full_indicesa.lower_bound(precalcb[i]);
		if (it != not_full_indicesa.end()) {
		  int k = *it;
		  ++acx[k];
		  if (acx[k] == mid) {
		    not_full_indicesa.erase(it);
		  }
		  ass[i] = true;
	    } else {
	      return false;
	    }
	  }
	}
	return true;
  };
  int lo = 1, hi = 1e6, ind = -1;
  while (lo <= hi) {
	int mid = (lo + hi) / 2;
	if (ok(mid)) {
	  ind = mid;
	  hi = mid - 1;
	} else lo = mid + 1;
  }
  return ind;
}

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