Cod sursa(job #2974059)

Utilizator zarg169Roxana zarg169 Data 2 februarie 2023 23:29:52
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
//https://www.infoarena.ro/problema/radixsort
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
vector <int> buckets[100005];
vector <int> sorted;

void radix(int n) {
    int x = 100000;
    for (int i = 0; i < n; ++i) {
        buckets[sorted[i] % x].push_back(sorted[i]);
    }
    sorted.clear();
    for (int j = 0; j < x; ++j) {
        for (int k = 0; k < buckets[j].size(); ++k) {
            sorted.push_back(buckets[j][k]);
            
        }
        buckets[j].clear();
    }

    for (int i = 0; i < n; ++i) {
        buckets[sorted[i] / x].push_back(sorted[i]);
    }
    sorted.clear();
    for (int j = 0; j < x; ++j) {
        for (int k = 0; k < buckets[j].size(); ++k) {
            sorted.push_back(buckets[j][k]);
        }
        buckets[j].clear();
    }         
}

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

    int N, A, B, C;
    fin >> N >> A >> B >> C;
    sorted.reserve(N);
    sorted.push_back(B);

    for (int i = 2; i <= N; ++i) {
        sorted.push_back((1LL * A * sorted.back() + B) % C);
    }

    radix(N);
    for (int i = 0; i < N; i += 10) {
        fout << sorted[i] << " ";
    }
}