Hint: Binary search!!

Solution: This is a pretty easy binary search problem. All we need is to check for every number of the second list(as first list is sorted in ascending order) let's denote as x, if we can find y = 10000-x in the first list. If we find y for any x(from the 2nd list) then we will print "YES". Because we already got a pair x, y for which x + y = 10000.

So, the complexity is NlogN(as we are doing binary search for every element of a list in the worst case).

---Spoiler---
Code:

/*
    author: Asif Anwar Sajid
*/
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector< int > v;
    for(int i=0; i<n; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }
    int m;
    cin >> m;
    bool flag = false;
    for(int i=0; i<m; i++) {
        int x; cin >> x;
        int y = 10000-x;
        if(binary_search(v.begin(), v.end(), y)) flag = true;
    }
    if(flag) cout << "YES\n";
    else cout << "NO\n";
}

int main()
{
    int t;
    t = 1;
    while(t--){
        solve();
    }
    return 0;
}

Edited by author 03.04.2021 11:52