E. Fair Share

[Link](Problem - E - Codeforces)

meaning of the title

Here you are m m m arrays and two multiple sets L , R L, R 50. R, it is required that each element in each array only belongs to L , R L,R 50. One in R, and half of all elements of each array belong to L L L half belongs to R R R. And will m m After m arrays are divided L L L set must be equal to R R The R set is the same element.

thinking

First, the number of occurrences of each element must be an even number. If it is not an even number, then at last L , R L,R 50. R must be different. One more element and one less element must be different.

Consider two key properties, half of each array L L L half R R R. Because in the end L = = R L==R L==R, so each element needs half L L L half R R R. We need to find a way to construct a partition scheme that conforms to this property.

We put the array aside and the elements aside, and connect each array with its elements with an undirected edge. Because all the array lengths are even and all the elements are even, there is an Euler loop in the graph, and we will put it in the loop number group → element element of edge Edges of array \ to elements Array → put the edges of elements into a collection, element element → number group of edge Element \ to the edge of the array The edges of element → array are put into another set. Because the degrees of all points are even, half of all edges satisfying the points belong to one set and the other half belong to another set, meeting the two properties of the condition.

​ a i a_i ai is big, but n n n is not big, so it's a little h a s h hash hash once, even the side can be used t u p l e : three element group tuple: triple tuple: triple, directly record his position in the answer, and divide it directly after traversing. When searching the Euler circuit, traverse all points (possibly multiple connected graphs) and do a deep search. Pay attention to deleting while searching, otherwise it will T T T.

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 4e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m, k;
int a[N];
vector<tuple<int, int, int>> g[N];
vector<bool> ok[N];
vector<int> res[N];
map<int, int> id;
int cnt, val;
void add(int u, int v, int x, int y) {
    g[u].push_back({v, x, y});
    g[v].push_back({u, x, y});
}
void dfs(int u) {
    while (g[u].size()) {
        auto [v, x, y] = g[u].back();
        g[u].pop_back();
        if (ok[x][y]) continue ;
        ok[x][y] = true;
        res[x][y] = val;
        val ^= 1;
        dfs(v);
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> m;
    cnt = m;
    for (int i = 1; i <= m; i ++) {
        cin >> n;
        res[i].resize(n), ok[i].resize(n);

        for (int j = 0; j < n; j ++) {
            int x; cin >> x;
            if (!id[x]) id[x] = ++ cnt;
            add(i, id[x], i, j);
        }
    }
    
    for (int i = 1; i <= cnt; i ++)
        if (g[i].size() % 2) {
            cout << "NO" << endl;
            return 0;
        }

    for (int i = 1; i <= cnt; i ++)
        dfs(i);
        
    cout << "YES" << endl;
    for (int i = 1; i <= m; i ++) {
        for (auto x : res[i])
            cout << (x ? "R" : "L");
        cout << endl;
    }
    return 0;
}