Cod sursa(job #2707429)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 16 februarie 2021 23:40:19
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <bits/stdc++.h>

using namespace std;

class InParser{
public:
    FILE *f;
    char *buff;
    int sp;
    char read_ch(){
        sp++;
        if(sp == 4096) {sp = 0;fread(buff, 1, 4096, f);}
        return buff[sp];
    }
public:
    InParser(const char* nume){
        f = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }
    InParser& operator >> (int &n){
        char c;
        while(!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if(c == '-') {n = 0;sgn = -1;}
        else n = c - '0';
        while(isdigit(c = read_ch())) n = n * 10 + c - '0';
        n *= sgn;
        return *this;
    }
};

class OutParser{
private:
    FILE *g;
    char *buff;
    int sp;
    void write_ch(char ch){
        if(sp == 50000){
            fwrite(buff, 1, 50000, g);
            sp = 0;
            buff[sp++] = ch;
        }
        else buff[sp++] = ch;
    }
public:
    OutParser(const char *name){
        g = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser(){
        fwrite(buff, 1, sp, g);
        fclose(g);
    }
    OutParser& operator << (int vu32){
        if(vu32 <= 9) write_ch(vu32 + '0');
        else {(*this) << (vu32 / 10);write_ch(vu32 % 10 + '0');}
        return *this;
    }
    OutParser& operator << (char ch){
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch){
        while(*ch) {write_ch(*ch);ch++;}
        return *this;
    }
};

InParser f("radixsort.in");
OutParser g("radixsort.out");

int get_byte(int x, int byte){
	return x >> (byte * 8) & 255;
}

void countSort(int a[], int b[], int N, int byte){
	int count[256], index[256];

	memset(count, 0, sizeof(count));

	for(int i = 1;i <= N;i++)
		count[get_byte(a[i], byte)]++;

	index[0] = 0;
	for(int i = 1;i < 256;i++)
		index[i] = index[i - 1] + count[i - 1];

	for(int i = 1;i <= N;i++)
		b[++index[get_byte(a[i], byte)]] = a[i];
}

void radixsort(int a[], int N){

	int *temp = new int [N + 1];
	for(int i = 0;i < 4;i++)
		if(i & 1) countSort(temp, a, N, i);
		else countSort(a, temp, N, i);

	delete[] temp;
}

int main(){

	int N, A, B, C;
	f >> N >> A >> B >> C;

	int *a = new int[N + 1];
	a[1] = B % C;
	for(int i = 2;i <= N;i++)
		a[i] = (1LL * A * a[i - 1] + B) % C;

	radixsort(a, N);

	for(int i = 1;i <= N;i += 10)
		g << a[i] << " ";

	delete[] a;
}