Cod sursa(job #1317795)

Utilizator retrogradLucian Bicsi retrograd Data 15 ianuarie 2015 10:23:53
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

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

#define MAXN 10000000
#define MOD 2150000

struct Elem {
    long val, ap;
    Elem(long v) {
        val = v;
        ap = 1;
    }
    Elem() {}
};

long n;
long long cur, a, b, c;
vector<Elem> H[MOD];
vector<Elem>::iterator it;

bool cmp(const Elem &a, const Elem &b) {
    return a.val<b.val;
}

void add(long x) {
    for(it = H[x/1000].begin(); it!=H[x/1000].end(); ++it) {
        if((*it).val == x) {
        (*it).ap++;
        return;
        }
    }
    H[x/1000].push_back(Elem(x));
}


int main() {
    fin>>n>>a>>b>>c;
    cur = b;
    for(int i=1; i<=n; i++, cur = (cur*a+b)%c) {
        add(cur);
    }
    for(int i=0; i<MOD; i++) {
        sort(H[i].begin(), H[i].end(), cmp);
    }
    long apcur = 0, curno = 1;
    for(int i=0; i<MOD; i++) {
        for(it=H[i].begin(); it!=H[i].end(); ++it) {
            apcur += (*it).ap;
            while(apcur >= curno) {
                fout<<(*it).val<<" ";
                curno += 10;
            }
        }
    }
}