OJ Board

Nazmul Quader Zinnuree wrote:No sorting & no hashing.

I used a flag array to identify duplicates..

Code: Select all

char flag[20000002]

It runs within 0:07.125

#include <iostream.h>
#include <string.h>
char flag[20000005]={0};
const int dif=10000005;
int main()
{	
	long long s,temp,k,t,n,ii,i,zz,zibil;
	cin>>t;
	for(ii=1;ii<=t;ii++)
	{
		zibil=2*ii-1;
		cin>>n>>k;
		s=0;
		long long b[505]={0};
		for(i=0;i<n;i++)
		{
			cin>>zz;			
			if(flag[zz+dif]==zibil+1) continue;
			if(flag[zz+dif]==zibil)
			{
				if(zz<0) temp=(k-(zz*-1)%k)%k;
				if(zz>=0) temp=zz%k;
				temp*=temp; temp%=k;
				s+=(temp==0);
				flag[zz+dif]++;
			}
			if(flag[zz+dif]<zibil)
			{
				if(zz<0) b[(k-(zz*-1)%k)%k]++;
				if(zz>=0) b[zz%k]++;
				flag[zz+dif]=zibil;
			}
		}
		s+=b[0]*(b[0]-1)/2;
		for(i=1;i<=k/2;i++)
		{ 
			if(i!=k-i) s+=b[i]*b[k-i];
			if(i==k-i) s+=b[i]*(b[i]-1)/2;
		}
		cout<<"Case "<<ii<<": "<<s<<endl;
	}
	return 0;
}

sunny wrote:can u pls describe ur algo a little bit.

%k and store necessary data in a 500 size array and for testing repeat data u can use flag array of size 20000002.

Remember,never try to initialize the full flag array for each test case. Handle it intelligently.

Abednego wrote:I got 3 seconds with read(0, buf, 1024*1024) and a linear-time algorithm.

Nazmul Quader Zinnuree wrote:make the flag array ready for the next input. re - initialize it with 0's

Stummer wrote:I don't need initialize it with 0's, because I use different flags for each
test case, i. e. I use flags 1 and 2 for test case 1, 3 and 4 for test case 2
and so... I changed char[20000005] to unsigned char[20000005] but
got WA again

Sumon wrote:

Stummer wrote:I don't need initialize it with 0's, because I use different flags for each
test case, i. e. I use flags 1 and 2 for test case 1, 3 and 4 for test case 2
and so... I changed char[20000005] to unsigned char[20000005] but
got WA again

In my implementation, at the end of each test case i have reset values to 0 of those index which i have changed in current test case.

I don't know your idea. I think you are missing some special cases. I couldn't configure the solution with the use of two(1,2) flag in one test case for managing all situation. I had to use three(0,1,2) flags in one test case. If you come to the point that you will use 3 flag then be careful, as test case range is 100 then you have to flag which is at most 300 according to your approach and you cannot store it in unsigned char also.

Stummer wrote:Yes, I use 3 flag, but in this way:
Let program works for case #X(from 1 to 100);
Than I use f1=2*X flag for elements which are not unique, f2=2*X-1
flag for elements which are unique yet, and f0<2*X-1 for elements which
are not exist yet. So in the next test case all my 2*X and 2*X-1 flags
becomes f0. And maximum flag is 200. If you don't understand anything,
just say me, or watch my program...
I tired with getting WA on this problem.

Sumon wrote: Sample Input:

5
5 5
5 5 5 5 5
4 4
2 2 4 0
3 4
2 2 4
5 4
2 2 4 0 4
5 4
-1 3 -3 1 1

Sample Output

Case 1: 1
Case 2: 2
Case 3: 1
Case 4: 3
Case 5: 4

Abednego wrote:I don't know. There might be some assembly language tricks that work better. It's the fastest that I know of.

Abednego wrote:I got 3 seconds with read(0, buf, 1024*1024) and a linear-time algorithm. It also helps not to store the numbers that you read. Read them one at a time and throw them away immediately.