// limli-full
#include <bits/stdc++.h>
#include "gift.h"
using namespace std;
typedef pair<int, int> ii;
vector<ii> combine(vector<ii> ranges) {
vector<ii> ans;
if (ranges.empty()) return ranges;
sort(ranges.begin(), ranges.end());
int a = ranges[0].first, b = ranges[0].second;
for (ii range : ranges) {
if (range.first <= b) {
b = max(b, range.second);
} else {
ans.push_back(ii(a, b));
a = range.first;
b = range.second;
}
}
ans.push_back(ii(a, b));
return ans;
}
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
vector<ii> ones, twos;
for (int i = 0; i < r; i++) {
ii range = ii(a[i], b[i]);
if (x[i] == 1) {
ones.push_back(range);
} else {
twos.push_back(range);
}
}
ones = combine(ones);
for (ii range : twos) {
if (range.first == range.second) {
return 0;
}
if (ones.empty()) continue;
int bs = upper_bound(ones.begin(), ones.end(), ii(range.first, 1000000000)) - ones.begin() - 1;
if (bs < 0) continue;
if (ones[bs].first <= range.first && range.second <= ones[bs].second) {
return 0;
}
}
string ans(n, 'R');
int pos = 0;
for (int i = 1; i < n; i++) {
if (!ones.empty() && ones[pos].first <= i - 1 && i <= ones[pos].second) {
ans[i] = ans[i - 1];
} else {
ans[i] = 'R' + 'B' - ans[i - 1];
}
if (pos + 1 < (int)ones.size() && ones[pos].second <= i) {
pos++;
}
}
craft(ans);
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
360 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
768 KB |
Output is correct |
5 |
Correct |
259 ms |
20068 KB |
Output is correct |
6 |
Correct |
272 ms |
20068 KB |
Output is correct |
7 |
Correct |
262 ms |
20068 KB |
Output is correct |
8 |
Correct |
261 ms |
20052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
6 ms |
768 KB |
Output is correct |
4 |
Correct |
197 ms |
16996 KB |
Output is correct |
5 |
Correct |
230 ms |
16996 KB |
Output is correct |
6 |
Correct |
199 ms |
16360 KB |
Output is correct |
7 |
Correct |
203 ms |
16344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
360 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
288 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
360 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
360 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
768 KB |
Output is correct |
5 |
Correct |
259 ms |
20068 KB |
Output is correct |
6 |
Correct |
272 ms |
20068 KB |
Output is correct |
7 |
Correct |
262 ms |
20068 KB |
Output is correct |
8 |
Correct |
261 ms |
20052 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
6 ms |
768 KB |
Output is correct |
12 |
Correct |
197 ms |
16996 KB |
Output is correct |
13 |
Correct |
230 ms |
16996 KB |
Output is correct |
14 |
Correct |
199 ms |
16360 KB |
Output is correct |
15 |
Correct |
203 ms |
16344 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
360 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
288 KB |
Output is correct |
23 |
Correct |
1 ms |
256 KB |
Output is correct |
24 |
Correct |
0 ms |
256 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
360 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
384 KB |
Output is correct |
35 |
Correct |
5 ms |
1300 KB |
Output is correct |
36 |
Correct |
5 ms |
1428 KB |
Output is correct |
37 |
Correct |
19 ms |
1924 KB |
Output is correct |
38 |
Correct |
248 ms |
18144 KB |
Output is correct |
39 |
Correct |
257 ms |
18064 KB |
Output is correct |
40 |
Correct |
256 ms |
18140 KB |
Output is correct |
41 |
Correct |
252 ms |
18200 KB |
Output is correct |
42 |
Correct |
232 ms |
18056 KB |
Output is correct |