#include <bits/stdc++.h>
using namespace std;

int main(){
    int n1,n2;
    int a[n1],b[n2];
    cin>>n1;
    for(int k=0;k<n1;k++) cin>>a[k];
    cin>>n2;
    for(int k=0;k<n2;k++) cin>>b[k];
    sort(a,a+n1);
    sort(b,b+n2);
    int i=0,j=n2-1;
    bool ans=false;
    while(i<n1&&j>=0){
        if(a[i]+b[j]==10000){
            ans=true;
            break;
        }
        else if(a[i]+b[j]>10000){
            j--;
        }
        else{
            i++;
        }
    }
    if(ans) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

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).

[Code was deleted]

Edited by moderator 06.06.2021 03:06

Что проверяет 5 тест(

o = 0
k = int(input())
a = [0] * (65536*2)
for i in range(k):
    a[int(input()) + 32768] = 1
h = int(input())
for i in range(h):
    if a[10000 - int(input()) + 32768] != 0:
        o += 1
if o >= 1:
    print('YES')
else:
    print('NO')

type
a = array[1..50000] of integer;
b = array[1..50000] of integer;


  Var c,d,i,k,g: integer;
  Var n: a; Var p: b;

  begin
  d:= 0;
  read(c);
  for i:= 1 to c do read(n[i]);
  read(k);
  for i:= 1 to k do read(p[i]);

  for i:=1 to c do
  for g:=1 to k do
  begin
  if (n[i] + p[g] = 10000) then
  begin
  writeln('YES');
  exit;
  end
  else if (i = c) and (g = k) and (n[i] + p[g] <> 10000) then
  begin
  writeln('NO');
  exit;
  end;
  end;
  end.

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = (int) 1e5 + 10;
int a[maxn], b[maxn];

int main() {
    int n, m;
    cin >> n;
    fo(i, n) cin >> a[i];
    int x, pos, ans;
    cin >> m;
    fo(i, m) {
        cin >> x;
        x = 10000 - x;
        ans = (int)1e9;
        pos = lower_bound(a, a + n, x) - a;
        for (int i = max(0, pos - 1), end = min(n - 1, pos + 1); i <= end; ++i) ans = min(ans, abs(x - a[i]));
        if (!ans) {
            cout << "YES\n";
            re 0;
        }
    }
    cout << "NO\n";
    re 0;
}

Edited by author 25.09.2016 18:07

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int m,n,a[50000],b[50000],i,j,p,c;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
    for(j=0;j<n;j++)
    {
        for(p=0;p<m;p++)
        {
            c=a[j]+b[p];

            if(c==10000)
            {
                 printf("YES");
                 exit(0);
            }
        }
    }
    printf("NO");
    return 0;
}

What's wrong?
Please, answer me.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    bool z;
    vector <int> so(0), st(0);
    unsigned int a;
    cin >> a;
    while (so.size() < a) {
        int soe;
        cin >> soe;
        so.push_back(soe);
    }
    unsigned int b;
    cin >> b;
    while (st.size() < b) {
        int ste;
        cin >> ste;
        st.push_back(ste);
    }

    for (unsigned int i = 0; i < so.size(); i++)
        for (unsigned int j = 0; j < st.size(); j++) {
            if (so[i] + st[j] == 10000) {
                z = true;
            }
        }
    if (z == true) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }

}

Edited by author 24.10.2015 04:23

Where is my wrong?
Why runtime error (access violation)?
This is my code-
program _1021;
var
  n,i,k,l,m:integer;
  a,b:array[1..10000] of integer;
begin
  read(n);
  for i:=1 to n do
  read(a[i]);
  read(m);
  for k:=1 to m do
  read(b[k]);
  for i:=1 to n do
  for k:=1 to m do
  if a[i]+b[k]=10000 then
  l:=l+1;
  if l>=1 then writeln('YES')
  else
  writeln('NO');
end.

[delete]

Edited by author 07.05.2014 10:53

Edited by author 07.05.2014 10:53

/*
 * File:   main.cpp
 * Author: Maxim Cherchuk <maxim.cherchuk@gmail.com>
 *
 * Created on 12 Февраль 2014 г., 23:36
 */


#include <iostream>
#include <algorithm>

using namespace std;

/*
 *
 */

const int MAXN = 50000, MAX = 10000;
int a[MAXN], b[MAXN];
int n, k, m;

int main(int argc, char** argv) {
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    cin >> k;
    for(int i = 0; i < k; ++i) {
        cin >> b[i];
    }
    sort(a, a+n);
    sort(b, b+k);
    for(int i = 0; i < n; ++i) {
        const int cur = a[i];
        int l = 0;
        int r = k;
        while(r-l > 1) { // binary search
            m = (l+r)>>1;
            if(cur+b[m] > MAX)
                r = m;
            else
                l = m;
        }
        if(cur + b[l] == MAX) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
}

Where do I have a problem?

I used binary search and got time limit on test 2. But when I use N*N1 speed I pass test 2 and get time limit on test 10.

Can you please check my code. I believe it is correct.


#include <iostream>

using namespace std;

bool binary_search (long* b , long a , long from ,long to)
{
    while (from != to)
    {
        long mid = (from + to )/2;
        if (b[mid] + a == 10000) return true;
        if (b[mid] + a > 10000)
        {
            from = mid;
        }
        if (b[mid] + a < 10000)
        {
            to = mid;
        }
    }
    return false;
}
int main ()
{
    long n , n1;
    long* a , *b;
    cin >> n;
    a = new long[n];
    for (int i =0 ; i < n ; i++)
    {
        cin >> a[i];
    }
    cin >> n1;
    b = new long[n1];
    for (int i =0 ; i < n1 ; i++ )
    {
        cin >> b[i];
    }
    bool tr = false;
    for (int i = 0 ; i < n ; i++)
    {
        tr = binary_search (b , a[i] , 0 , n1);
        if (tr) break;
    }
    if(tr) cout << "YES";
    else cout << "NO";
}

#include<iostream>
using namespace std;

short a[50001],b[50001];
int N,M,index_1_0,index_1_10,index_2_0,index_2_10;
bool f_0,f_10,t_0,t_10;
const int T=10000;

int main()
{
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>a[i];
        if(a[i]>=0&&!f_0)
        {
            index_1_0=i;
            f_0=true;
        }
        if(a[i]>=1000&&!f_10)
        {
            index_1_10=i;
            f_10=true;
        }
    }
    cin>>M;
    for(int i=0;i<M;i++)
    {
        cin>>b[i];
        if(b[i]<=0&&!t_0)
        {
            index_2_0=i;
            t_0=true;
        }
        if(b[i]<=1000&&!t_10)
        {
            index_2_10=i;
            f_10=true;
        }
    }
    for(int i=0;i<=index_1_0;i++)
    {
        for(int j=0;j<=index_2_10;j++)
        {
            if(a[i]+b[j]<1000)
            break;
            if(a[i]+b[j]==T)
            {
                cout<<"YES";
                return 0;
            }
        }
    }
    for(int i=index_1_0;i<=index_1_10;i++)
    {
        for(int j=index_2_10;j<=index_2_0;j++)
        {
            if(a[i]+b[j]<1000)
            break;
            if(a[i]+b[j]==T)
            {
                cout<<"YES";
                return 0;
            }
        }
    }
    for(int i=index_1_10;i<N;i++)
    {
        for(int j=index_2_0;j<M;j++)
        {
            if(a[i]+b[j]<1000)
            break;
            if(a[i]+b[j]==T)
            {
                cout<<"YES";
                return 0;
            }
        }
    }
    cout<<"NO";
    }

Edited by author 28.06.2013 11:46

I've got WA:



Var a,b:array[1..1000]of longint;n,k,i,j,o:shortint;
begin
o:=0;
read(n);
for i:=1 to n do read(a[i]);
read(k);
for j:=1 to k do read(b[j]);
for i:=1 to n do
for j:=1 to k do
if a[i]+b[j]=10000 then o:=1;
if o=0 then write('NO');
if o=1 then write('YES');
end.

Edited by author 29.03.2013 19:42

Try the following 2 tests:

2
0
10000
2
20000
10000

and

2
0
10000
2
0
-10000

What answer is issued by your program?

Edited by author 14.02.2013 20:37

#include<iostream>
#include<cmath>

using namespace std;

int a1[100000],a2[100000];
int main()
{
    int n1,n2;
    cin>>n1;
    for (int i=1; i<=n1; i++) cin>>a1[i];
    cin>>n2;
    for (int i=1; i<=n2; i++) cin>>a2[i];
    int i=1,j=1;
    bool bk=false;
    while (i<=n1 || j<=n2)
    {
        if (a1[i]+a2[j]==10000)
        {
            bk=true;
            break;
        }
        if (a1[i]+a2[j]<10000)
          if (i==n1) break; else i++;
        else
          if (j==n2) break; else j++;
    }
    if (bk==false) cout<<"NO"<<endl;
       else cout<<"YES"<<endl;
    return 0;
}

Please add this test

2
1
10000
1
1

my program showed YES this test but Accepted