Cod sursa(job #2974013)

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

using namespace std;
int const MAX = 10000001;
int arr[MAX];
vector <pair<int, pair<int, int>>> buckets[100005];
vector <pair<int, pair<int, int>>> sorted;

void radix(int arr[], int n) {
    pair<int, int> keyNumber;
    int x = 100000;
    for (int i = 1; i <= n; ++i) {
        keyNumber.first = int(arr[i] / x);
        keyNumber.second = arr[i] % x;
        buckets[keyNumber.second].push_back({arr[i], {keyNumber.first, keyNumber.second}});
    }
    for (int j = 0; j < x; ++j) {
        if (buckets[j].empty()) continue;
        for (int k = 0; k < buckets[j].size(); ++k) {
            sorted.push_back(buckets[j][k]);
            
        }
        buckets[j].clear();
    }
    int y = 100;
    for (int i = 0; i < n; ++i) {
        sorted[i].second.first = int(sorted[i].second.first / 100);
        sorted[i].second.second = sorted[i].second.first % 100;
        buckets[sorted[i].second.second].push_back({sorted[i].first, {sorted[i].second.first, sorted[i].second.second}});
    }
    sorted.clear();
    for (int l = 0; l < 101; ++l) {
        if (buckets[l].empty()) continue;
        for (int m = 0; m < buckets[l].size(); ++m) {
            sorted.push_back(buckets[l][m]);
        }
        buckets[l].clear();
    }
}

// void radix(int arr[], int n) {
//     pair<int, int> keyNumber;
//     int x = 100000;
//     for (int i = 1; i <= n; ++i) {
//         keyNumber.first = int(arr[i] / x);
//         keyNumber.second = arr[i] % x;
//         buckets[keyNumber.second].push_back({arr[i], {keyNumber.first, keyNumber.second}});
//     }
//     for (int j = 0; j < x; ++j) {
//         if (buckets[j].empty()) continue;
//         for (int k = 0; k < buckets[j].size(); ++k) {
//             sorted.push_back(buckets[j][k]);
            
//         }
//         buckets[j].clear();
//     }
//     int condition = 3;
//     while (condition != 0) {
//         for (int i = 0; i < n; ++i) {
//             sorted[i].second.first = int(sorted[i].second.first / 10);
//             sorted[i].second.second = sorted[i].second.first % 10;
//             buckets[sorted[i].second.second].push_back({sorted[i].first, {sorted[i].second.first, sorted[i].second.second}});
//         }
//         sorted.clear();
//         for (int l = 0; l <= 9; ++l) {
//             for (int m = 0; m < buckets[l].size(); ++m) {
//                 sorted.push_back(buckets[l][m]);
//             }
//             buckets[l].clear();
//         }
//         condition -= 1;
//     }       
// }

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

    int N, A, B, C;
    fin >> N >> A >> B >> C;
    arr[1] = B;

    for (int i = 1; i <= N; ++i) {
        arr[i] = (A * arr[i-1] + B) % C;
    }

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