/**
* For x[i] = 1, the whole range should be the same. Therefore, after considering all
* x[i]=1 we would've obtained a series of subranges, each of which should be
* monochromatic. It suffices to color the subranges one by one in alternating color.
*
* Time Complexity: O(n + r)
* Implementation 1
*/
#include <bits/stdc++.h>
#include "gift.h"
typedef std::vector<int> vec;
int construct(int n, int r, vec a, vec b, vec x) {
vec x1_a, x1_b;
for (int i = 0; i < r; i++) {
if (x[i] == 1) {
x1_a.push_back(a[i]);
x1_b.push_back(b[i]);
}
}
std::sort(x1_a.begin(), x1_a.end());
std::sort(x1_b.begin(), x1_b.end());
int m = x1_a.size();
vec parent(n, -1);
for (int pos = 0, i = 0, j = 0, current = -1, layer = 0; pos < n; pos++) {
while (j < m && x1_b[j] < pos)
j++, layer--;
if (layer > 0)
parent[pos] = current;
else
current = -1;
while (i < m && x1_a[i] <= pos)
i++, layer++;
if (layer > 0)
current = pos;
}
std::string color;
for (int pos = 0, c = 0; pos < n; pos++) {
if (parent[pos] == -1) {
color.push_back(c == 0 ? 'R' : 'B');
c ^= 1;
} else {
color.push_back(color[parent[pos]]);
}
}
vec red_count(n + 1);
red_count[0] = 0;
for (int i = 0; i < n; i++)
red_count[i + 1] = red_count[i] + (color[i] == 'R');
bool possible = true;
for (int i = 0; i < r && possible; i++) {
int reds = red_count[b[i] + 1] - red_count[a[i]];
int blues = b[i] - a[i] + 1 - reds;
assert(reds >= 0 && blues >= 0);
if (x[i] == 1)
possible &= (reds == 0 || blues == 0);
else
possible &= (reds > 0 && blues > 0);
}
if (possible)
craft(color);
return possible;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
4 ms |
852 KB |
Output is correct |
5 |
Correct |
204 ms |
29140 KB |
Output is correct |
6 |
Correct |
238 ms |
29176 KB |
Output is correct |
7 |
Correct |
259 ms |
29180 KB |
Output is correct |
8 |
Correct |
216 ms |
29176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
3 ms |
736 KB |
Output is correct |
4 |
Correct |
139 ms |
24652 KB |
Output is correct |
5 |
Correct |
143 ms |
24796 KB |
Output is correct |
6 |
Correct |
132 ms |
24160 KB |
Output is correct |
7 |
Correct |
138 ms |
24136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
0 ms |
316 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
224 KB |
Output is correct |
5 |
Correct |
1 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
4 ms |
852 KB |
Output is correct |
5 |
Correct |
204 ms |
29140 KB |
Output is correct |
6 |
Correct |
238 ms |
29176 KB |
Output is correct |
7 |
Correct |
259 ms |
29180 KB |
Output is correct |
8 |
Correct |
216 ms |
29176 KB |
Output is correct |
9 |
Correct |
0 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
736 KB |
Output is correct |
12 |
Correct |
139 ms |
24652 KB |
Output is correct |
13 |
Correct |
143 ms |
24796 KB |
Output is correct |
14 |
Correct |
132 ms |
24160 KB |
Output is correct |
15 |
Correct |
138 ms |
24136 KB |
Output is correct |
16 |
Correct |
1 ms |
304 KB |
Output is correct |
17 |
Correct |
0 ms |
316 KB |
Output is correct |
18 |
Correct |
0 ms |
316 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
300 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
300 KB |
Output is correct |
28 |
Correct |
1 ms |
224 KB |
Output is correct |
29 |
Correct |
1 ms |
320 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
7 ms |
5348 KB |
Output is correct |
36 |
Correct |
8 ms |
5392 KB |
Output is correct |
37 |
Correct |
15 ms |
6216 KB |
Output is correct |
38 |
Correct |
176 ms |
26572 KB |
Output is correct |
39 |
Correct |
175 ms |
26056 KB |
Output is correct |
40 |
Correct |
206 ms |
26444 KB |
Output is correct |
41 |
Correct |
179 ms |
26492 KB |
Output is correct |
42 |
Correct |
208 ms |
26060 KB |
Output is correct |