11321 - Sort! Sort!! and Sort!!!

[Orion]

Hi, can someone give me a hand on this problem, i got WA , i just used a sort with the criteria explained in the problem:

the function used to compare:

Code: Select all

int modcmp (int *a, int *b) {
 
 int m1 = *a % m;
 int m2 = *b % m;
 if (m1 != m2)
  return m1 - m2;
  
 if ( (*a % 2) == 0 ) {
  if ( (*b %2) == 0)
   return *a - *b;  // when both are even the smaller precede the larger
  else
   return 1;   // the second precede the first since the second is odd
 }
 else {
   if ((*b%2) == 0)
    return -1; // the first precede the second since the first is odd 
   else
    return *b - *a; // when both are odd the larger precede the smaller
 }
}

the sort:

Code: Select all

  qsort ( (void *) seq, n, sizeof(int), (int (*)(const void*, const void*)) (modcmp));

can anyone give me a hint or some critical test cases ?

Thank you very much

[Robert Gerbicz]

Hi, can someone give me a hand on this problem, i got WA , i just used a sort with the criteria explained in the problem:

the function used to compare:

Code: Select all

int modcmp (int *a, int *b) {
...
   return *a - *b;  // when both are even the smaller precede the larger
...

Please note that the numbers are int, so -2^31<x,y<2^31 it means that -2^32<x-y<2^32 so you will get nice overflow for int type, and it gives you WA. Try to use <,> symbols in your function.

[Orion]

Hi, can someone give me a hand on this problem, i got WA , i just used a sort with the criteria explained in the problem:

the function used to compare:

Code: Select all

int modcmp (int *a, int *b) {
...
   return *a - *b;  // when both are even the smaller precede the larger
...

Please note that the numbers are int, so -2^31<x,y<2^31 it means that -2^32<x-y<2^32 so you will get nice overflow for int type, and it gives you WA. Try to use <,> symbols in your function.

Thanks for your reply, thats true the overflow was the problem, now i got
AC

Thank you

[anikolov]

I had the same problem. After reading the post above, I changed the subtractions to comparisons and the judge accepted.

[Ron]

im getting TLE.....
please !! help me ..... what should i do ???????

Code: Select all

 Code Accepted ... !!

thnk to sapnil !!

[Orion]

i recommend you to use the sort () algorithm in <algorithm> or qsort in <cstdlib> with the criteria specified in the problem instead of implementing your own, and try not to use and sort three arrays, you just need one array

[sapnil]

Yes use qsort function of C;
>> Just modified this function &
make sure that it alyaws return integer.

Thanks
Keep posting
Sapnil

[RC's]

I used linked list but I got WA...
Is there anyone who has tricky input ?

[sapnil]

Try This cases

Input:
6 5
10
20
30
50
60
70
6 5
5
15
25
35
45
55
6 5
5
10
15
20
25
30
0 0
Output:
6 5
10
20
30
50
60
70
6 5
55
45
35
25
15
5
6 5
25
15
5
10
20
30
0 0

Thanks
Keep posting
Sapnil

[TimeString]

although i have accepted this problem, but i wonder what's the bug in my previous code.

Code: Select all

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

long long int en,em;

int mod(long long int n,long long int m){
	if(n>0)
		return n%m;
	else
		return m-(-n)%m;
}

int cmp2(long long int a,long long int b){
	if(a<b)
		return -1;
	else if(a>b)
		return 1;
	else
		return 0;
}

int cmp(long long int *a,long long int *b){
	long long int ta,tb;
	long long int taa,tab;
	ta=*a%em;
	tb=*b%em;
	taa=mod(*a,2);
	tab=mod(*b,2);
	if(ta!=tb)
		return ta-tb;
	else{
		if(taa!=tab)
			return tab-taa;
		else{
			if(taa==1)
				return cmp2(*b,*a);
			else
				return cmp2(*a,*b);
		}
	}
}

int main(){
	int i;
	long long int einfo[10010];
	while(scanf("%lld%lld",&en,&em),en>0){
		printf("%lld %lld\n",en,em);
		for(i=0;i<en;i++)
			scanf("%lld",&einfo[i]);
		qsort(einfo,en,sizeof(long long int),(int (*) (const void*,const void*))cmp);
		for(i=0;i<en;i++)
			printf("%lld\n",einfo[i]);
	}
	printf("0 0\n");
	return 0;
}

after i changed all of "long long int" to "int" and got AC.

[Kallol]

where is it wrong , plz ??

Code: Select all

Removed after AC

[TimeString]

the problem says the operation mod should exactly follow C language, so you needn't to determine whether a number is positive or negitive.

but when you have to determine a number is odd or not, use should carefully use mod operation, because a negative odd number mod 2 returns -1.

[missbus]

Code: Select all

#include <cstdlib>
#include <iostream>

using namespace std;

#define MSIZE 10003

struct qq
{
	int ori,mod;
}q[MSIZE];

int modcomp(const void *a, const void *b)
{
	qq *q1 = (qq*) a;
	qq *q2 = (qq*) b;
	
	return q1->mod - q2->mod;
}

int upcomp(const void *a, const void *b){
	return (*(int *)a) - (*(int*)b);
	
}

int dncomp(const void *a, const void *b){
	return (*(int *)b) - (*(int*)a);
}

int main()
{
	int modkind[MSIZE];
	int odd[MSIZE], even[MSIZE];
	int N, M;
    int count, modsize;
    int ptr;
    
	while(cin >> N >> M && N != 0 || N != 0){
		for(count = 0; count < N; count++) {
			cin >> q[count].ori;
			q[count].mod = q[count].ori % M;			
		}
		
		qsort(q, N, sizeof(qq), modcomp);	
        
		for(int i = 0; i < MSIZE; i++)
			modkind[i] = 0;
		modkind[0] = 1;
		modsize = 1;
		for(int i = 0; i < N - 1; i++){
			if(q[i].mod != q[i+1].mod){
				modsize++;
				modkind[modsize-1]++;
			}
			else 
				modkind[modsize-1]++;
		}
		
		for(int i = 0; i < MSIZE; i++){
			odd[i] = 0;
			even[i] = 0;
		}
			
		ptr = 0;
		int ansodd[modsize][MSIZE], anseven[modsize][MSIZE];
		for(int k = 0; k < modsize; k++){
			for(int j = 0; j < modkind[k]; j++){	
				if(q[ptr].ori % 2 != 0){
					ansodd[k][odd[k]] = q[ptr].ori;
					odd[k]++;
				}
				else{
					anseven[k][even[k]] = q[ptr].ori;
					even[k]++;
				}
				ptr++;
			}
			
		}
		
		for(int p = 0; p < modsize; p++){
			qsort(ansodd[p], odd[p], sizeof(int), dncomp);
			qsort(anseven[p], even[p], sizeof(int), upcomp);
		}
		
			cout << N << " " << M << endl;
				for(int y = 0; y < modsize; y++){
					for(int z = 0; z < odd[y]; z++)
						cout << ansodd[y][z] << endl;
					for(int z = 0; z < even[y]; z++)
						cout << anseven[y][z] << endl;
				}
	}
			cout << 0 << " " << 0 << endl;
	return 0;
	
}

I don't know what's wrong in my code.
It gets a lot of runtime errors.
But I have use many test data and it outputs right answers.
Can anyone explain this strange status.
Please help me, thanks a lot.

[naffi]

Why Runtime Error???
I cant find the error.
Can u?

Code: Select all

#include<iostream> 
#include<algorithm>
#include<vector>

using namespace std;

class nums
{
	public:
		long long int v;
		long long int m;
		
		nums(){}
		nums(long long int val,long long int mod)
		{
			v = val;
			m = mod;
		}
		bool operator<(nums f)
		{
			return m < f.m;
		}
		bool operator>(nums f)
		{
			return m > f.m;
		}
		bool operator==(nums f)
		{
			return m == f.m;
		}
};

bool comp(nums f, nums s)
{
	if(f > s)return false;
	else if(f < s)return true;
	else
	{
		if(f.v%2 && s.v%2)
		{
			if(f > s)return true;
			else false;
		}
		else if(!(f.v%2) && !(s.v%2))
		{
			if(f < s)return true;
			else false;
		}
		else
		{
			if(f.v%2)return true;
			else false;
		}		
	}
}

vector <nums> values;

main()
{
#ifndef ONLINE_JUDGE
	freopen("input","r",stdin);	
	freopen("output","w",stdout);
#endif
	int n,m,x;
	long long int temp;
	while(cin>>n>>m && n != 0)
	{
		x = n;
		while(x--)
		{
			cin>>temp;
			values.push_back(nums(temp,temp%m));
		}
		sort(values.begin(),values.end(),comp);
		cout<<n<<" "<<m<<endl;
		for(x = 0; x < values.size(); x++)cout<<values[x].v<<endl;
		values.resize(0,nums());
	}
	cout<<"0 0"<<endl;
}

Thanks Mr. Sohel.

[naffi]

I changed vector to array, but cant get rid off runtime error.
any reason???
please help to get it AC.