#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    3
    Rep 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. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,376
    Rep Power
    1871
    Please edit your post and put [code][/code] tags around your code.
    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
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    OK, I'll take a whack at it.

    The program implements radix sort.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo