Cod sursa(job #1946577)

Utilizator AkrielAkriel Akriel Data 30 martie 2017 11:04:01
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 5.97 kb
#include <bits/stdc++.h>

#define type long long int

/**

                                          `-.`'.-'
                                       `-.        .-'.
                                    `-.    -./\.-    .-'
                                        -.  /_|\  .-
                                    `-.   `/____\'   .-'.
                                 `-.    -./.-""-.\.-      '
                                    `-.  /< (()) >\  .-'
                                  -   .`/__`-..-'__\'   .-
                                ,...`-./___|____|___\.-'.,.
                                   ,-'   ,` . . ',   `-,
                                ,-'   ________________  `-,
                                   ,'/____|_____|_____\
                                  / /__|_____|_____|___\
                                 / /|_____|_____|_____|_\
                                ' /____|_____|_____|_____\
                              .' /__|_____|_____|_____|___\
                             ,' /|_____|_____|_____|_____|_\
,,---''--...___...--'''--.. /../____|_____|_____|_____|_____\ ..--```--...___...--``---,,
                           '../__|_____|_____|_____|_____|___\
      \    )              '.:/|_____|_____|_____|_____|_____|_\               (    /
      )\  / )           ,':./____|_____|_____|_____|_____|_____\             ( \  /(
     / / ( (           /:../__|_____|_____|_____|_____|_____|___\             ) ) \ \
    | |   \ \         /.../|_____|_____|_____|_____|_____|_____|_\           / /   | |
 .-.\ \    \ \       '..:/____|_____|_____|_____|_____|_____|_____\         / /    / /.-.
(=  )\ `._.' |       \:./ _  _ ___  ____  ____ _    _ _ _ _ _  _ __\        | `._.' /(  =)
 \ (_)       )        \/                                            \       (       (_) /
  \    `----'          """"""""""""""""""""""""""""""""""""""""""""""        `----'    /
   \   ____\__                                                              __/____   /
    \ (=\     \                                                            /     /-) /
     \_)_\     \                                                         /     /_(_/
          \     \                                                        /     /
           )     )  _                                                _  (     (
          (     (,-' `-..__                                    __..-' `-,)     )
           \_.-''          ``-..____                  ____..-''          ``-._/
            `-._                    ``--...____...--''                    _.-'
                `-.._                                                _..-'
                     `-..__         AKRIEL KNOWS ALL           __..-'
                           ``-..____                  ____..-''
                                    ``--...____...--''

*/

using namespace std;

class parser{
    private:
        fstream inputFile;
        static const int SIZE = 0x200000;
        char buffer[SIZE];
        int index = 0;

        inline void incrementation(){
            index++;
            if ( index == SIZE ){
                index = 0;
                inputFile.read(buffer, SIZE);
            }
        }

    public:
        parser() {}

        parser(const char *fileName){
            inputFile.open(fileName, ios::in | ios::binary);
            inputFile.sync_with_stdio(false);
            index = 0;
            inputFile.read(buffer, SIZE);
        }

        inline parser &operator >> (int &number){
            for ( ; buffer[index] <'0' or '9' < buffer[index]; incrementation() );

            number = 0;
            for ( ; '0' <= buffer[index] and buffer[index] <= '9'; incrementation() )
                number = 10*number + buffer[index]-'0';
            return *this;
        }

        ~parser(){
        inputFile.close();
        }
};

class writer{
    private:
        fstream outputFile;
        static const int SIZE = 0x200000;
        int index = 0, aux, number;
        char buffer[SIZE], charNumber[24];

        inline void incrementation(){
            index++;
            if ( index == SIZE ){
                index = 0;
                outputFile.write(buffer, SIZE);
            }
        }

    public:
        writer() {}

        writer(const char *fileName){
            outputFile.open(fileName, ios::out | ios::binary);
            outputFile.sync_with_stdio(false);
            index = 0;
        }

        inline writer &operator << (int target){
            aux = 0;
            number = target;
            if ( number == 0 ){
                charNumber[aux] = '0';
                aux++;
            }

            for ( ; number; number/=10 ){
                charNumber[aux] = number%10 + '0';
                aux++;
            }

            for ( ; aux; incrementation() ){
                aux --;
                buffer[index] = charNumber[aux];
            }
            return *this;
        }

        inline writer &operator << (const char *target){
            aux = 0;
            for ( ; target[aux]; ){
                buffer[index] = target[aux];
                aux++;
                incrementation();
            }
            return *this;
        }

        ~writer(){
            outputFile.write(buffer,SIZE);
            outputFile.close();
        }
};

parser fin ("radixsort.in");
ofstream fout ("radixsort.out");

const int N = 10000005;

int totalNumbers;

int numbers[N], first, second, third;

inline void readVariables(){
    fin >> totalNumbers >> first >> second >> third;

    numbers[1] = second;
    for ( int index = 2; index <= totalNumbers; index++ ){
        numbers[index] = ( 1LL*first*numbers[index-1] + second) % third;
    }
}

inline void printSolution(){
    for ( int index = 1; index <= totalNumbers; index+=10 )
        fout << numbers[index] << " ";
}

int main(){
    readVariables();
    stable_sort(numbers+1, numbers+totalNumbers+1);
    printSolution();
}