#include <bits/stdc++.h>
#include "gift.h"
using namespace std;
struct Requirement {
int start, end, type;
};
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
vector<pair<int, int>> forced_same_intervals;
vector<Requirement> different_color_reqs;
// 1. Separate requirements into 'must be same' and 'must be different'
for (int i = 0; i < r; ++i) {
if (x[i] == 1) {
forced_same_intervals.push_back({a[i], b[i]});
} else {
different_color_reqs.push_back({a[i], b[i], x[i]});
}
}
// 2. Merge overlapping 'same color' intervals
sort(forced_same_intervals.begin(), forced_same_intervals.end());
vector<pair<int, int>> merged;
for (auto& interval : forced_same_intervals) {
if (merged.empty() || interval.first > merged.back().second) {
merged.push_back(interval);
} else {
merged.back().second = max(merged.back().second, interval.second);
}
}
// 3. Assign Group IDs based on merged intervals
// Items in the same merged interval share a group ID.
// Boundaries between groups are where color changes can happen.
vector<int> group_id(n);
int current_group = 0;
int next_item_to_process = 0;
for (auto& interval : merged) {
// Fill items before the interval with unique groups
while (next_item_to_process < interval.first) {
group_id[next_item_to_process++] = current_group++;
}
// Fill the interval itself with one group
for (int i = interval.first; i <= interval.second; ++i) {
group_id[i] = current_group;
}
next_item_to_process = interval.second + 1;
current_group++;
}
// Fill remaining items
while (next_item_to_process < n) {
group_id[next_item_to_process++] = current_group++;
}
// 4. Validate 'must be different' requirements
// If a range [start, end] is within the same group_id,
// it's impossible to have different colors.
for (auto& req : different_color_reqs) {
if (group_id[req.start] == group_id[req.end]) {
return 0; // Contradiction found
}
}
// 5. Build the result string by alternating colors
string result = "";
for (int i = 0; i < n; ++i) {
result += (group_id[i] % 2 == 0) ? 'B' : 'R';
}
craft(result);
return 1;
}
