Submission #1165173

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1165173	2025-03-11 08:11:03	tesseract	Robots (IOI13_robots)	C++20	100 / 100	652 ms	21044 KiB

robots

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "robots.h"
#include <algorithm>
#include <functional>
#include <ranges>
#include <vector>
#include <cassert>
using namespace std;
/* We order all the robots in a single sequence as follows: All the weak
 * robots in *increasing* order of their weight limits, followed by all
 * the small robots in *decreasing* order of their size limits. This way,
 * for each toy, if one looks at the set of robots which can pick up that
 * toy, it forms a contiguous subinterval of the sequence of all robots.
 *
 * At this point, one can rephrase the problem as follows: You are given T
 * subintervals of [0,N) (where N = A + B). For each such interval, you
 * have to choose an integer point in it as its chosen point. For each i
 * in [0, N), the weight of i is the number of intervals for which it has
 * been chosen. Choose points to minimize the maximum weight of all elements
 * of [0, N). Note that in this formulation we don't reference any of the
 * weight or size limits, and we don't make distinction between weak and
 * small robots.
 */
// Interval of integers [L, U).
struct Interval {
  int L, U;
  inline int length() const { return U-L; }
};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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