#include "gift.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> #define pii pair <int, int> #define tiii tuple <int, int, int> #define tiiii tuple <int, int, int, int> #define emb emplace_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define iShowSpeed cin.tie(NULL)->sync_with_stdio(false) #define matrix vector <vector <int>> #define mat(n, m) vector <vector <int>> (n, vector <int> (m)); const int mod = 1e9 + 7; const int inf = 1e9; const matrix II = {{1, 0}, {0, 1}}; const int N = 5e5 + 5; int par[N]; int dsu(int a){ return par[a] = (a == par[a] ? a : dsu(par[a])); } int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) { iota(par, par + N, 0ll); int cnt[3] = {0}; for (int i = 0; i < r; i++) { cnt[x[i]]++; } if (cnt[1] == r) { string ss(n, 'R'); craft(ss); return 1; } if (cnt[2] == r) { string ss = ""; for (int i = 0; i < r; i++) if (a[i] == b[i]) return 0; for (int i = 0; i < n; i++) { if (i % 2) ss += "R"; else ss += "B"; } craft(ss); return 1; } string s(n, ' '); for (int i = 0; i < r; i++) { if (x[i] == 1) { for (int j = a[i]; j <= b[i]; j++) { if (j < b[i]) par[dsu(j)] = dsu(j + 1); s[j] = 'R'; } } } for (int i = 0; i < r; i++) { if (x[i] == 2) { if (dsu(a[i]) == dsu(b[i])) return 0; } } for (int i = 0; i < n; i++) { if (s[i] != ' ') continue; int j = i, idx = 0; while (j < n && s[j] == ' ') { if (idx % 2 == 0) s[j] = 'B'; else s[j] = 'R'; idx++; j++; } i = j - 1; } craft(s); return 1; } /* sub 1: x[i] = 1 just output all "R" sub 2: x[i] = 2 if (a[i] == b[i]) : return 0; else return alternating sequence sub 3: 1 <= n,r <= 18 sub 4: 1 <= n,r <= 2000 sub 5: full sol */