Why when I use <algo.h> this fuckin' compiler can't load it!!!!

Just use binary search.
Becase the teacher's list is in ascending order.
We can solve the problem in O(mlogn).

My solution is:



#include <iostream>
//#include <conio.h>
using namespace std;
int prepod[15000], n;
int binsearch(int num)
{
    int l = 0, r = n - 1, m;
    while (r - l > 1)
    {
        int m = (r + l) / 2;
        if (prepod[m] == num)
          return 1;
        if (prepod[m] > num)
            l = m;
        if (prepod[m] > num)
            r = m;
    }
    if ((prepod[l] != num) && (prepod[r] != num))
      return 0;
    else
      return 1;
}
int main()
{
    int m, student, s=0;
    cin>>n;
    for (int i = 0; i < n; i++)
      scanf ("%i", &prepod[i]);
    cin>>m;
    for (int i = 0; i < m; i++)
    {
        scanf ("%i", &student);
        s+=binsearch (student);
    }
    cout<<s;
    //getch();
    return  0;
}


And it has time O(mlogn) and it is about 9e+6.

I've sent 2 times - it's Crash
Can anyone help???

numbers in Teachers list can be repeated.
for example for this test:
2
1
1
3
1
1
1
Answer: 3
(your program probably gives 6 and that's why fails it)

var tech : array [1..15000] of longint;
    pupil: array [1..1000000] of longint;
    i,m,n,kol:longint;
Procedure Find(k:longint);
Var l,r:longint;
begin
  l:=1;
  r:=m;
  while true do begin
    if k < pupil[(l+r) div 2] then
     begin
       if r=(l+r) div 2 then break;
       r:=(l+r) div 2;
     end
      else
    if k > pupil[(l+r) div 2] then
     begin
       if l=(l+r) div 2 then break;
       l:=(l+r) div 2;
     end
      else
    if k = pupil[(l+r) div 2] then begin inc(kol); l:=(l+r) div 2 + 1; end;
  end;
end;

Procedure Quick(l,r:longint);
Var i,j,k,q:longint;
begin
 i:=l; j:=r; k:=pupil[(l+r) div 2];
 repeat
   while pupil[i] < k do inc(i);
   while pupil[j] > k do dec(j);
   if i<=j then
    begin
      q:=pupil[i];
      pupil[i]:=pupil[j];
      pupil[j]:=q;
      inc(i);
      dec(j);
    end;
 until i>j;
 if r > i then Quick(i,r);
 if l < j then Quick(l,j);
end;

begin
 kol:=0;
 read(n);
 for i:=1 to n do read(tech[i]);
 read(m);
 for i:=1 to m do read(pupil[i]);
 Quick(1,m);
 for i:=1 to n do
  find(tech[i]);
 writeln(kol);
end.

This code work normal on my PC:
#include <iostream.h>

void main()
{
    int i=0;long int j=0;
    long int rez = 0;
    cin>>i;
    long int pr[15000];
    for(long int k = 0; k<i; k++)
    {
        cin>>pr[k];
    }
    cin>>j;
    long int tmp =0;
    for(k = 0; k<j; k++)
    {
        cin>>tmp;
        for(int m = 0; m<i; m++)
        {
            if(tmp==pr[m])
            {rez++;}
        }
    }
    cout << rez;
}

BUT WHY WA??

#include<stdio.h>


int main()
{
    int n,m,p,q,r,i;
    int count=0;
    int t[15000];
    int k;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&t[i]);

  scanf("%d",&m);

    for(i=0;i<m;i++)
    {
        scanf("%d",&k);
        p=0;
        r=n-1;
        while(p<=r)
         {
              q=(p+r)/2;
               if(t[q]==k)
               {
                count++;
                p=q+1;

            }
            else if(t[q]<k)
                p=q+1;
            else
                r=q-1;
        }


    }

    printf("%d\n",count);

    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
void main()
{
int v[15000],s,z=0,i,j,n,st,t;
cin>>n;
for (i = 0; i <=n-1; i++) cin>>v[i];
cin>>st;
for (i = 0; i <=st-1; i++)
{
cin>>s;
if(binary_search(v,v+n,s)==true)z++;
}
cout<<z;
}

import java.io.*;
import java.util.*;
public class FindinArray_1196{
    public static int binarySearch( int  a[], int x )
        {
            int low = 0;
            int high = a.length - 1;
            int mid;

            while( low <= high )
            {
                mid = ( low + high ) / 2;

                if( a[ mid ] < x )
                    low = mid + 1;
                else if( a[ mid ] > x )
                    high = mid - 1;
                else
                    return mid;
            }

            return -1;     // NOT_FOUND = -1
        }


public static void main(String args[])
{
    Scanner sc=new Scanner(System.in);
    int count=0;

    int n=sc.nextInt();
    int arr[]=new int[n];


    for(int i=0;i<n;i++)
    {
        arr[i]=sc.nextInt();
    }


    int m=sc.nextInt();
    int brr[]=new int[m+1];

    for(int i=0;i<m;i++)
    {
        brr[i]=sc.nextInt();
    }




    for(int i=0;i<m;i++)
    {



            if(binarySearch(arr,brr[i])!=-1)
            count++;




    }


    System.out.println(count);


}
}

i have confusing why i use set(STL). i got WA in case #1. but when i write it in normal binary search it can AC.

Edited by author 09.04.2008 11:58

But I think, it is cheating...

Edited by author 08.04.2007 03:01

WA: Memory limit exceeded...


Edited by author 30.08.2007 12:47

Edited by author 30.08.2007 12:47

program History_Exam_1196_sub2;

{$APPTYPE CONSOLE}
var arr:array[0..66000] of boolean;
n,c,cou,sov:longint;
begin
 readln(n);
 for cou:=1 to n do
 begin
 readln(c);
 arr[c]:=true;
 end;
 readln(n);
 for cou:=1 to n do
 begin
 readln(c);
 if arr[c]=true then inc(sov);
 end;
 writeln(sov);

end.

I used the following O(m) algorithm, where 'a' - teacher's list, 'b' - student's list.
I got WA on test 10. After sorting _teacher's_(!) list as well, program was accepted. Therefore, it seems that 10th test has a bug. Am I right, or maybe missed smth?
It seems this bug wasn't mentioned before, 'cause general approach is not O(m), but O(m*ln(n)) solution, which uses O(n) memory. And that approach may work somehow..

Arrays.sort(b);
int c = 0;
int j = 0;
for (int i = 0; i < a.length; i++) {
    if (i > 0 && a[i] == a[i - 1]) continue;
    while (j < b.length && b[j] < a[i]) {
        j++;
    }
    while (j < b.length && b[j] == a[i]) {
        c++;
        j++;
    }
}
cout.println(c);

I Wonder why I have to sort in advance the elements in the array of the teacher in order to use binary_search otherwise I get WA

#include<iostream.h>
#include<fstream.h>
int main()
{
long teach[25005],stud[200005];
long i,j,kol=0,k,l,r,n,m;
cin>>n;
for(i=1;i<=n;i++)cin>>teach[i];
cin>>m;
for(i=1;i<=m;i++)
{
    cin>>stud[i];
    l=1;r=n;
    for(j=1;j<=m;j++)
    {
    if(stud[i]<teach[1])break;else
    {
    k=(l+r)/2;
    if(stud[i]>teach[k])l=k+1;else
    if(stud[i]<teach[k])r=k-1;else {kol++;break;}
    }
    }
}cout<<kol;
return 0;
}