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

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Orion
New poster
Posts: 3
Joined: Sun Oct 21, 2007 1:18 am

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

Post by Orion » Sun Oct 21, 2007 1:28 am

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
Last edited by Orion on Sun Oct 21, 2007 7:44 am, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11321 - Sort! Sort!! and Sort!!!

Post by Robert Gerbicz » Sun Oct 21, 2007 1:41 am

Orion wrote: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.
Last edited by Robert Gerbicz on Sun Oct 21, 2007 1:42 am, edited 1 time in total.

Orion
New poster
Posts: 3
Joined: Sun Oct 21, 2007 1:18 am

Re: 11321 - Sort! Sort!! and Sort!!!

Post by Orion » Sun Oct 21, 2007 1:50 am

Robert Gerbicz wrote:
Orion wrote: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
Last edited by Orion on Sun Oct 21, 2007 7:43 am, edited 1 time in total.

anikolov
New poster
Posts: 7
Joined: Sun Oct 21, 2007 1:38 am

Post by anikolov » Sun Oct 21, 2007 6:29 am

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

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

why TLE

Post by Ron » Sun Oct 21, 2007 4:06 pm

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

Code: Select all

 Code Accepted ... !!
thnk to sapnil !!
Last edited by Ron on Sun Dec 30, 2007 9:34 pm, edited 1 time in total.

Orion
New poster
Posts: 3
Joined: Sun Oct 21, 2007 1:18 am

Post by Orion » Mon Oct 22, 2007 12:59 am

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
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Mon Oct 22, 2007 10:51 am

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

Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's » Tue Oct 23, 2007 11:24 am

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

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Tue Oct 23, 2007 4:41 pm

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
"Dream Is The Key To Success"

@@@ Jony @@@

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

long long int get WA ??

Post by TimeString » Thu Dec 06, 2007 4:37 pm

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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Jan 12, 2008 5:33 pm

where is it wrong , plz ??

Code: Select all

Removed after AC
Last edited by Kallol on Mon Jan 14, 2008 4:21 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Sun Jan 13, 2008 8:33 am

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
New poster
Posts: 3
Joined: Tue Feb 27, 2007 3:44 pm

Runtime error!!!!!!

Post by missbus » Sun Jan 27, 2008 9:01 pm

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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Location: BUET, Bangladesh
Contact:

11321.....Sort Sort Sort.......Why Runtime Error???

Post by naffi » Wed Mar 19, 2008 8:21 pm

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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Location: BUET, Bangladesh
Contact:

Runtime Error Running

Post by naffi » Sun Mar 23, 2008 10:12 pm

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

Post Reply

Return to “Volume 113 (11300-11399)”