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

Moderator: Board moderators

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

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

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!!!

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!!!

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
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

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
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:
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
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:
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 ??

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
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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
TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 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!!!!!!

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

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

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