Expert.
Put your skills to the test.

Problem summary

For each of five pairs of sequences with distinct elements within each sequence, decide whether both can be subsequences of one sequence whose elements are all distinct.

Constraints

Each sequence has 1 to 100000 distinct values between 1 and 1000000000.

Worked example

Official sample; other valid outputs may exist.

3 1 2 3
4 1 3 5 6
3 5 1 4
4 150 1 20 5
4 1 5 6 2
3 2 1 6
5 100 20 45 10 3
4 3 100 80 10
5 90 1 4 8 80
5 90 1 8 100 5

10001

Solution analysis

1. Only elements common to both sequences can impose conflicting order constraints. Record each value’s position in the first sequence, using an ordered map.
2. Scan the second sequence, skipping values absent from the first. The positions of the remaining values must be strictly increasing. A decrease means the two sequences require opposite orders for a pair of shared values.
3. In the first sample pair the common values are 1 and 3 in the same order, so insert the private elements around them. In the second, 5 precedes 1 in the first sequence but follows 1 in the second, so merging is impossible.

Why it works

Any common supersequence preserves the order of shared values, proving necessity. If their order agrees, use these values as anchors. Between each consecutive pair of anchors, append the private first-sequence block followed by the private second-sequence block. No private value occurs in both, so this construction has distinct elements and contains both input sequences, proving sufficiency.

Watch out. This is subsequence merging, not contiguous substring merging. Values common to both must occur only once in the result.

An independently written complete program with standard headers.

// Key idea: Any common supersequence preserves the order of shared values, proving necessity. If their
// order agrees, use these values as anchors.
#include<iostream>
#include<map>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int test=0;test<5;++test){
        int n;
        cin>>n;
        map<int,int>position;
        for(int i=0;i<n;++i){
            int x;
            cin>>x;
            position[x]=i;
        }
        int m;
        cin>>m;
        bool possible=true;
        int previous=-1;
        for(int i=0;i<m;++i){
            int x;
            cin>>x;
            auto it=position.find(x);
            if(it!=position.end()){
                if(it->second<=previous){
                    possible=false;
                }
                previous=it->second;
            }
        }
        cout<<(possible?'1':'0');
    }
    cout<<'\n';
}