my program works well for the first 8 . gives a WA on 9.
i m using binary search . the code follows

#include<iostream>
#include<stdlib.h>

using namespace std;

int binarysearch(long num,int a[],int lb,int ub,int order) {
  //cout<<"\nbinarysearch "<<lb<<" "<<ub<<" "<<num<<" "<<order;
  //cout<<"\nhi";
  int mid = (lb + ub)/2;
  if(lb >= ub)
    return -1;
  if(a[mid] == num)
    return mid;
  else {
    if(a[mid] < num) {
      if(order == 1)
    binarysearch(num,a,mid+1,ub,order);
      else
    binarysearch(num,a,lb,mid-1,order);
    }
    else {
      if(order == -1)
    binarysearch(num,a,mid+1,ub,order);
      else
    binarysearch(num,a,lb,mid-1,order);
    }
  }
}

main() {

  int n1,n2;
  int a1[50000],a2[50000];

  cin>>n1;
  for(int i = 0;i < n1;i++)
    cin>>a1[i];
  cin>>n2;
  for(int i = 0;i < n2;i++)
    cin>>a2[i];
//      cout << "the last number in a2 is " << a2[n2-1] << endl;
//    cout << "n1 and n2 are " << n1 << " and " << n2 << endl;

  if(a1[n1-1]+a2[0] < 10000) {
    cout<<"NO";
//    cout << "no because greatests sum < 10000" << endl;
    exit(0);
  }
  if(a1[0] + a2[n2-1] > 10000) {
    cout<<"NO";
//    cout << "no because smallests sum > 10000" << endl;
//    cout << "the smallests are " << a1[0] << " and " << a2[n2-1] << endl;
   exit(0);
  }

  if(n1 < n2) {
    for(int i = 0;i < n1;i++)
      if(binarysearch(10000-a1[i],a2,0,n2,-1) != -1) {
    cout<<"YES";
    exit(0);
      }
  }
  else {
    for(int i = 0;i < n2;i++)
      if(binarysearch(10000-a2[i],a1,0,n1,1) != -1) {
    cout<<"YES";
    exit(0);
      }
  }
  cout<<"NO";
//    cout << "no reason" << endl;
  return 0;
}

You do not have to realize binary search in this problem.
Use boolean vector from -32768 to 32767.

Edited by author 04.08.2004 23:45