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

//#define MAX 10001
void quicksort(long long[],int,int);
int partition(long long[],int,int);
void swap(long long[],int,int);

int main()
{
 int t,k,q,i,j,qi,c,p;
 long long *mot,*sat,*res;
 //printf("Enter no of test cases");
 scanf("%d",&t);
 for(i=0;i<t;i++)
 {
  p=0;
  //printf("Enter no of chefs and no of queries");
  scanf("\n%d %d",&k,&q);
  mot=(long long*)malloc(k*sizeof(long long));
  sat=(long long*)malloc(k*sizeof(long long));
  res=(long long*)malloc(k*k*sizeof(long long));
  //printf("Enter motivation levels");
  for(j=0;j<k;j++)
  scanf("%lld",&mot[j]);
  //printf("Enter satisfaction levels");
  for(j=0;j<k;j++)
  scanf("%lld",&sat[j]);
  //calc sum[]
  for(c=0;c<k;c++)
  for(j=0;j<k;j++)
  res[p++]=mot[c]+sat[j];
free(mot);
free(sat);
  quicksort(res,0,p-1);       //partition,swap
  for(j=0;j<q;j++)
  {
   //printf("\n qith lowest sum");
   scanf("%d",&qi);
   if(qi<=(k*k))
   printf("%lld\n",res[qi-1]);
  }
 free(res);
 }
 return 0;
}

void quicksort(long long *sum,int low,int high)
{
 int m;
 if(low<high)
 {
  m=partition(sum,low,high);
  quicksort(sum,low,m-1);
  quicksort(sum,m+1,high);
  }
}

int partition(long long *sum,int low,int high)
{
 long long pivot=sum[low];
 int i=low,j=high;
 while(i<j)
 {
  while(sum[i]<=pivot&&i<high)
  i++;
  while(sum[j]>pivot)
  j--;
  if(i<j)
  swap(sum,i,j);
  }
  swap(sum,low,j);
  return j;
}

void swap(long long *sum,int i,int j)
{
 long long temp;
 temp=sum[i];
 sum[i]=sum[j];
 sum[j]=temp;
}

This is a code that i posted on codechef but i am getting this SIGSGEV error.I cracked my head a lot but in vain.
The constraints for the problem statement were
1 ≤ t ≤ 5
1 ≤ k ≤ 20000
1 ≤ q ≤ 500
1 ≤ qi ( for i = 1 to Q ) ≤ 10000
1 ≤ Ai ≤ 10^18 ( for i = 1 to K ) (value of element of mot[] can be)
1 ≤ Bi ≤ 10^18 ( for i = 1 to K ) (value of element of sat[] can be)

A segmentation fault means you accessed memory you don't own. The two most common causes are a pointer that's not properly initialized an an index outside the bounds of an array. Trace through your code and ensure that all of your pointers point to enough memory, then make sure all of your indexes are within those bounds.

still i am not getting it I have been working on it since 2 days now and still couldn't find anything

basically i posted the code on codechef.So i don't know for what input does it fail.But it works fine for small test cases.Now the constraints as i have mentioned above specify the limit for input data .So i think it would fail for some large value but i don't know which and how can we input such large value.(eg k=20,000)how can we input sat and mot for each chef?Also i have another doubt.Is there any fault in memory allocation i.e malloc cannot allocate large memory?

You are using a long long for the address, but you are only using integers for the position. Try something more appropriate for the function signatures, such as an unsigned long long (or size_t) for the low/high barriers. Also, look at the qsort() impementation for more hints/information.

i tried doing this

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

//#define MAX 10001
void quicksort(long long[],long long,long long);
int partition(long long[],long long,long long);
void swap(long long[],long long,long long);

int main()
{
 int t,k,q,i,j,qi,c;
 long long *mot,*sat,*res,p;
 //printf("Enter no of test cases");
 scanf("%d",&t);
 for(i=0;i<t;i++)
 {
  p=0;
  printf("Enter no of chefs and no of queries");
  scanf("%d %d",&k,&q);
 long long *mot=(long long*)malloc(k*sizeof(long long));
 long long *sat=(long long*)malloc(k*sizeof(long long));
 long long *res=(long long*)malloc(k*k*sizeof(long long));
  //printf("Enter motivation levels");
  for(j=0;j<k;j++)
  scanf("%lld",&mot[j]);
  //printf("Enter satisfaction levels");
  for(j=0;j<k;j++)
  scanf("%lld",&sat[j]);
  //calc sum[]
  for(c=0;c<k;c++)
  for(j=0;j<k;j++)
  res[p++]=mot[c]+sat[j];
free(mot);
free(sat);
  quicksort(res,0,p-1);       //partition,swap
  for(j=0;j<q;j++)
  {
   //printf("\n qith lowest sum");
   scanf("%d",&qi);
   if(qi<=(k*k))
   printf("%lld\n",res[qi-1]);
  }
 free(res);
 }
 return 0;
}

void quicksort(long long sum[],long long low,long long high)
{
 long long m;
 if(low<high)
 {
  m=partition(sum,low,high);
  quicksort(sum,low,m-1);
  quicksort(sum,m+1,high);
  }
}

int partition(long long sum[],long long low,long long high)
{
 long long pivot=sum[low];
 long long i=low,j=high;
 while(i<j)
 {
  while(sum[i]<=pivot&&i<high)
  i++;
  while(sum[j]>pivot)
  j--;
  if(i<j)
  swap(sum,i,j);
  }
  swap(sum,low,j);
  return j;
}

void swap(long long sum[],long long i,long long j)
{
 long long temp;
 temp=sum[i];
 sum[i]=sum[j];
 sum[j]=temp;
}

still failed and gave the same error as previous when i submitted

Questions:
1.CAN MALLOC allocate space for res
long long *res=(long long*)malloc(k*k*sizeof(long long));
when k=20,000
res would have 20,000*20,000 elements & space needed=400000000 * sizeof(long long)

2.I also tried static allocation for sat,mot and res
So does C support

long long res[10^9];

Edited 3 Years Ago by inspire_all

res would have 20,000*20,000 elements & space needed=400000000 * sizeof(long long)

Assuming the minimum size of long long, you're trying to allocate about 3GB of consecutive memory at one time. Chances are good the allocation will fail.

So does C support long long res[10^9];

No, the ^ operator represents binary XOR, not exponentiation. Static allocation of this amount of memory is even less likely to succeed due to stack size limits.

If you absolutely must sort that much data, I'd recommend looking into an external sorting algorithm rather than an in-memory algorithm. Or break down your data set into something manageable.

This article has been dead for over six months. Start a new discussion instead.