Cod sursa(job #2921961)

Utilizator tzancauraganuTzanca Uraganu tzancauraganu Data 2 septembrie 2022 17:23:39
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <sstream>
 
using namespace std;


ifstream f("radixsort.in");
ofstream g("radixsort.out");

 
int main() {
    unsigned int N, A, B, C;

    f >> N >> A >> B >> C;
    vector<unsigned int> v(N);
    v[0] = B;
    for (int i = 1; i < N; ++i) {
        v[i] = (1LL * A * v[i - 1] + B) % C;
    }

    vector<int> cnt(256);
    for (unsigned int p = 24, mask = 255 << p; mask > 0; mask >>= 8, p -= 8) {
        for (int i = 0; i < N; i++)
            ++cnt[(v[i] & mask) >> p];
        
        int i = 0;
        unsigned int revmask = ~mask;
        for (unsigned int c = 0; c < 256; c++) {
            unsigned int val = c << p;

            for (int count = cnt[c]; count > 0; --count) {
                v[i] = (v[i] & revmask) | val;
                i++;
            }
            cnt[c] = 0;
        }
    }

    stringstream s;
    for (int i = 0; i < N; i += 10)
        s << v[i] << ' ';
    s << '\n';

    g << s.str();
 
    f.close();
    g.close();
    return 0;
}