Submission #968633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
968633	2024-04-23T18:50:45 Z	mannshah1211	Robots (IOI13_robots)	C++17	100 / 100	1982 ms	29952 KB

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.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4440 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4532 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	554 ms	26292 KB	Output is correct
5	Correct	117 ms	19424 KB	Output is correct
6	Correct	207 ms	9388 KB	Output is correct
7	Correct	620 ms	23848 KB	Output is correct
8	Correct	483 ms	26276 KB	Output is correct
9	Correct	459 ms	25804 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4952 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4440 KB	Output is correct
11	Correct	1 ms	4440 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct

Subtask #4

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4544 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4600 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4544 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	14 ms	4812 KB	Output is correct
17	Correct	13 ms	5012 KB	Output is correct
18	Correct	7 ms	4956 KB	Output is correct

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4696 KB	Output is correct
10	Correct	581 ms	26548 KB	Output is correct
11	Correct	94 ms	19448 KB	Output is correct
12	Correct	204 ms	9228 KB	Output is correct
13	Correct	627 ms	23852 KB	Output is correct
14	Correct	495 ms	26316 KB	Output is correct
15	Correct	1 ms	4548 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4444 KB	Output is correct
18	Correct	1 ms	4444 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	4536 KB	Output is correct
21	Correct	14 ms	4956 KB	Output is correct
22	Correct	434 ms	25992 KB	Output is correct
23	Correct	433 ms	25832 KB	Output is correct
24	Correct	1897 ms	29952 KB	Output is correct
25	Correct	1902 ms	29508 KB	Output is correct
26	Correct	1103 ms	29896 KB	Output is correct
27	Correct	1982 ms	29368 KB	Output is correct
28	Correct	1905 ms	29384 KB	Output is correct
29	Correct	609 ms	29456 KB	Output is correct