Cod sursa(job #2737170)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 4 aprilie 2021 14:49:25
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
#define Byte(x) ((x >> (8 * byte)) & 255)

using namespace std;

class OutParser {
  private:
    vector<char> str;
    int ptr;
    ofstream fout;

    void putChar(char chr) {
        if (ptr == (int) str.size()) {
            fout.write(str.data(), str.size());
            ptr = 0;
        }
        str[ptr++] = chr;
    }

    template<class T>
    void putInt(T num) {
        if (num < 0) {
            putChar('-');
            num *= -1;
        }
        if (num > 9)
            putInt(num / 10);
        putChar(num % 10 + '0');
    }

  public:
    OutParser(const char* name) : str(1e5), ptr(0), fout(name) { }
    ~OutParser() { fout.write(str.data(), ptr); fout.close(); }

    template<class T>
    friend OutParser& operator<<(OutParser& out, const T num) {
        out.putInt(num);
        return out;
    }

    friend OutParser& operator<<(OutParser& out, const char chr) {
        out.putChar(chr);
        return out;
    }

    friend OutParser& operator<<(OutParser& out, const char* str) {
        for (int i = 0; str[i]; i++)
            out.putChar(str[i]);
        return out;
    }
};

ifstream fin("radixsort.in");
OutParser fout("radixsort.out");

const int N_MAX = 1e7 + 5;

int N, A, B, C;
int v[N_MAX];

void CountingSort(int byte)
{
    vector < int > aux[256];
    for (int i = 1; i <= N; i++) {
        aux[Byte(v[i])].push_back(v[i]);
    }

    int pos = 1;
    for (int mask = 0; mask < 256; mask++) {
        for (int i = 0; i < aux[mask].size(); i++) {
            v[pos++] = aux[mask][i];
        }
    }
}

void RadixSort()
{
    for (int byte = 0; byte < 4; byte++) {
        CountingSort(byte);
    }
}

int main()
{
    fin >> N >> A >> B >> C;
    v[1] = B;
    A %= C;
    B %= C;
    for (int i = 2; i <= N; i++) {
        v[i] = (1LL * v[i - 1] * A + B) % C;
    }
    RadixSort();
    for (int i = 1; i <= N; i += 10) {
        fout << v[i] << " ";
    }
    return 0;
}