Just check the my source code to figure it out how I did it. If you
consider yourself a lamer just copy & paste it into the submit form.

#include <stdio.h>
#include <stdlib.h>

int n, m;
int t[50000];

int main(void)
{
    int found = 0, pos = 0;

    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &t[i]);

    scanf("%d", &m);
    for(int i = 0; i < m && !found; i ++)
    {
        int tmp;
        scanf("%d", &tmp);

        while(tmp + t[pos] < 10000) pos ++;
        found |= tmp + t[pos] == 10000;
    }

    if(found) printf("YES\n");
    else printf("NO\n");
    return 0;
}

Hey Alex!

Here's mine, slightly faster - O( input size ), but uses more memory
(the traditional trade-off):

#include <stdio.h>

/* Bigger than needed, but oh well :) */
char used_nums[66000];
/* This one will point at the middle of the
 * above vector so that we can index negative
 * numbers. */
char *used;

int main() {
  int i, j, n;

  /* Make it point at the middle of the vector. */
  used = &used_nums[ 33000 ];

  scanf( "%d", &n );

  /* Mark off each number in the first list. */
  for( i = 0; i < n; i++ ) {
    scanf( "%d", &j );
    used[ j ] = 1;
  }

  scanf( "%d", &n );

  /* For each number in the second list... */
  for( i = 0; i < n; i++ ) {
    scanf( "%d", &j );

    /* Check if the corresponding number has been marked off... */
    if( 10000 - j > -32769 && 10000 - j < 32768 && used[ 10000 -
j ] ) {
      printf( "YES" );
      return;
    }
  }

  printf( "NO" );
}

/* Coded while listening to Dio & Yngwie Malmsteen - Dream On
(tribute to Aerosmith) */

> Just check the my source code to figure it out how I did it. If you
> consider yourself a lamer just copy & paste it into the submit form.
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int n, m;
> int t[50000];
>
> int main(void)
> {
>     int found = 0, pos = 0;
>
>     scanf("%d", &n);
>     for(int i = 0; i < n; i ++) scanf("%d", &t[i]);
>
>     scanf("%d", &m);
>     for(int i = 0; i < m && !found; i ++)
>     {
>         int tmp;
>         scanf("%d", &tmp);
>
>         while(tmp + t[pos] < 10000) pos ++;
>         found |= tmp + t[pos] == 10000;
>     }
>
>     if(found) printf("YES\n");
>     else printf("NO\n");
>     return 0;
> }
>
>

 if( 10000 - j > -32769 ...   is always true

Wrote while listening to "Tatoo" - "Do not trust, do not be afraid,
do not ask" ;-)

you realize that this isn't O(input size), right?

Edited by author 07.02.2006 18:50