11849 - CD

[diegon]

Is good to know that the disks id go up to 2 000 000. Just checked.

[AhmadKhatar]

Hi!
How can I speed up the code?
Thanks in advance!

[brianfry713]

http://acm.uva.es/board/viewtopic.php?t=67799

[uDebug]

brianfry713,

Thanks very much for these test cases.

[me33]

Getting run time error.
plz help...
my code.

Code: Select all

removed after AC. :D  :) 

[brianfry713]

I think you could make your arrays global, fixed size, and int to avoid RE, but then you'll probably get TLE. See the other threads on this problem. You can solve it in O(N + M) instead of O(N * M). Also scanf/printf is faster than cin/cout.

[me33]

Thanks brianfry713

[sajal2k8]

Why i am getting wrong answer? Here is my code:

Code: Select all

#include <iostream>

using namespace std;
 long long int nu[1000000],num[1000000];

 long long int matchCounter( long long int lottery[5],  long long int user[5],  long long int matches,  long long int SIZE)
{
     long long int count = 0;

    for (int count = 0; count < SIZE; count++)
    {
        if (lottery[count] == user[count])
        {
            matches++;
        }
}

    return matches;
}
int main()
{
     long long int a,b,c,i,j,sum=0;
    while(cin>>a>>b && (a!=0 || b!=0))
    {
        for(i=0;i<a;i++)
            cin>>nu[i];
        for(j=0;j<b;j++)
            cin>>num[j];

        if(a<b)
            c=a;
        else
            c=b;
        sum=matchCounter(nu,num,sum,c);
        cout<<sum<<endl;
        sum=0;
    }
    return 0;
}

Thanks in advance

[brianfry713]

Input:

Code: Select all

2 1
1
2
2
0 0

output should be 1

[amrondonp]

Just use 2 pointers instead a map.

Suppose we have 2 arrays sorted

a1 a2 ... an-1
b1 b2 ... bm-1

start with ans=0
and
pa=0 and pb=0 the indexes

if( a[pa] == b[pb] ) ans++

then you just advance the pointer in the array which has the least number (if they are equal no matter which you choose)
repeat whis while pa<n and pb<m