Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
September 28th, 2013, 02:45 AM
 Sarang235
Registered User

Join Date: Nov 2012
Posts: 1
Time spent in forums: 1 h 8 m 25 sec
Reputation Power: 0
Help me understand this code(beginner)

I am trying to solve a problem in codechef . It is about sorting large amount of numbers. When i used quicksort to sort them it showed that time limit exceeded. When i saw code of another contestant, I was not able to understand the code. Please help me in that.
here is the problem

Given the list of numbers, you are to sort them in non decreasing order.
Input

t – the number of numbers in list, then t lines follow [t <= 10^6].

Each line contains one integer: N [0 <= N <= 10^6]
Output

Output given numbers in non decreasing order.
Example

Input:

5
5
3
6
7
1

Output:

1
3
5
6
7

Time Limit: 5 sec
Source Limit: 50000 Bytes

and here is the solution i didnt get
Code:
``` #include <stdio.h>
#define BUFSIZE 32768
static char bin[BUFSIZE];
static char bot[BUFSIZE];
static int list[1000001];
int main(void)
{
int i, line;
int num = 0, lines = 0;
int r = fread(bin, sizeof(char), BUFSIZE, stdin);
for(i = 0; i < r && bin[i] >= '0'; i++) {
lines = (bin[i] - '0') + (10 * lines);
}
for(; i < r && bin[i] < '0'; i++);
for(line = lines; line > 0; i++){
if(i == BUFSIZE){
r = fread(bin, sizeof(char), BUFSIZE, stdin);
i = -1;
} else if(bin[i] >= '0'){
num = (bin[i] - '0') + (10 * num);
} else {
list[num]++;
num = 0;
line--;
}
}
for(i = line = 0; lines > 0; line++){
while(list[line]-- > 0){
if((i + 8) >= BUFSIZE){
fwrite(bot, sizeof(char), i, stdout);
i = 0;
}
num = line;
if (num < 100000){
if (num < 10000){
if (num < 1000){
if (num < 100){
if (num < 10){
bot[i++] = num + 48;
} else {
bot[i+1] = num - num / 10 * 10 + 48;
bot[i] = num / 10 + 48;
i += 2;
}
} else {
bot[i+2] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+1] = num - num / 10 * 10 + 48;
bot[i] = num / 10 + 48;
i += 3;
}
} else {
bot[i+3] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+2] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+1] = num - num / 10 * 10 + 48;
bot[i] = num / 10 + 48;
i += 4;
}
} else {
bot[i+4] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+3] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+2] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+1] = num - num / 10 * 10 + 48;
bot[i] = num / 10 + 48;
i += 5;
}
} else {
if (num < 1000000) {
bot[i+5] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+4] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+3] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+2] = num - num / 10 * 10 + 48;
num /= 10;
bot[i+1] = num - num / 10 * 10 + 48;
bot[i] = num / 10 + 48;
i += 6;
} else {
bot[i+6] = '0';
bot[i+5] = '0';
bot[i+4] = '0';
bot[i+3] = '0';
bot[i+2] = '0';
bot[i+1] = '0';
bot[i] = '1';
i += 7;
}
}
bot[i++] = '\n';
lines--;
}
}
if(i > 0){
fwrite(bot, sizeof(char), i-1, stdout);
}
return 0;
}```

#2
September 28th, 2013, 08:57 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,252
Time spent in forums: 2 Months 4 Weeks 1 Day 12 h 25 m 37 sec
Reputation Power: 1809
Copy again from your code editor so indentation is preserved.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

#3
October 1st, 2013, 11:02 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,124
Time spent in forums: 1 Month 3 Weeks 2 Days 4 h 49 m 23 sec
Reputation Power: 455
OK, I'll take a whack at it.

__________________
[code]Code tags[/code] are essential for python code!

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Help me understand this code(beginner)