Codeforces round 770 (Div. 2) e. fair share

subject

m(1<=m<=1e5) An array , The first i The length of arrays is ni（2<=ni<=2e5,ni For the even ）

The first i The... In the array j It's worth aij(1<=aij<=1e9),sumni<=2e5

Ask if you can divide these integers into two multiset, It might be called L The collection and R aggregate ,

So that exactly half of the elements in each array are L Within collection , The other half of the element is R Within collection ,

And L The collection and R The set is ultimately the same multiset

Source of ideas

palayutm、wifiii Code

Answer key

If you think of the structure of Euler circuit , It's easy to do

First, consider the case of no solution , A certain number appears an odd number of times , There must be no solution ; otherwise , There must be a solution

First discretize the numbers , Then here is a way of composition ：

The first i Array ,ai0 and ai1 Even without direction ,ai2 and ai3 Even without direction , And so on

amount to ai0 and ai1 On different sides of the bipartite graph ,ai2 and ai3 Empathy ,

You can find , For each point on the graph （ The number after discretization ） Come on ,

Because the number of occurrences is even , So the degree is even , So the Euler circuit must have a solution

In a certain scheme of Euler loop , edge x It's from No i An array of a Value points to b It's worth it ,

Orient the edges , Might as well give b Value divided into R aggregate , to a Value divided into L aggregate

No matter how the edges in the same array are oriented , Half of them belong to L, The other half belongs to R

And for every number v Come on , Just one half of it comes from v Starting point to other points , The other half starts from other points and returns v

Try it here c11 and c17 The grammar of , I think it's very good

Experience

Think in reverse , Why do you build a map like this ,

Because each number appears to be an even number , So each aij One side , It can ensure that the Euler circuit has a solution

Because there is just ni/2 One is located in L aggregate , another ni/2 One is located in R aggregate ,

So it's equivalent to ni/2 For mutual exclusion , It corresponds to building in each array ni/2 Pair the edges in pairs ,

When orienting the edge , Place adjacent points in different sets , That's how it works

This is related to the official explanation , Left point of bipartite graph i It means the first one i An array , On the right j Representation number j Mapping method , The essence is consistent

Code

#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main(){
    fast();
    int m,n;
    cin>>m;
    vector<vector<int> >a(m),ans(m);
    vector<int>b;
    for(int i=0;i<m;++i){
        cin>>n;
        a[i].resize(n);
        ans[i].resize(n);
        for(int j=0;j<n;++j){
            cin>>a[i][j];
            b.push_back(a[i][j]);
        }
    }
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    vector<int>deg(b.size());
    for(int i=0;i<m;++i){
        for(auto &v:a[i]){
            v=lower_bound(b.begin(),b.end(),v)-b.begin();
            deg[v]++;
        }
    }
    for(auto &v:deg){
        if(v&1){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    vector<vector<array<int,4>> >e(b.size());
    int id=0;
    for(int i=0;i<m;++i){
        for(int j=1;j<a[i].size();j+=2){
            e[a[i][j]].push_back({a[i][j-1],i,j,id});
            e[a[i][j-1]].push_back({a[i][j],i,j-1,id});
            id++;
        }
    }
    vector<bool>vis(id);
    function<void(int)> dfs = [&](int u){
        while(!e[u].empty()){
            auto [v,i,j,id]=e[u].back();
            e[u].pop_back();
            if(vis[id])continue;
            vis[id]=1;
            ans[i][j]=1;
            dfs(v);
        }
    };
    for(int i=0;i<b.size();++i){
        dfs(i);
    }
    cout<<"YES"<<endl;
    for(int i=0;i<m;++i){
        for(auto &v:ans[i]){
            cout<<(v?'L':'R');
        }
        cout<<endl;
    }
    return 0;
}