Cod sursa(job #2947624)

Utilizator cezarTriscaVicolCezar Trisca Vicol 2 cezarTriscaVicol Data 26 noiembrie 2022 14:42:01
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

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

int N,A,B,C;
vector<int> v;

void quick_sort(vector<int>& v){
    int n = v.size();
    if(n <= 1)
        return ;
    int mid = n/2;
    vector<int> a;
    vector<int> b;
    for(int i=0;i<mid;i++)a.push_back(v[i]);
    for(int i=mid;i<n;i++)b.push_back(v[i]);
    quick_sort(a);
    quick_sort(b);
    for(int i=0,j=0;(i<a.size())||(j<b.size());){
        if(i == a.size()){
            v[i+j] = b[j];
            j++;
        }else if(j == b.size()){
            v[i+j] = a[i];
            i++;
        }else if(a[i] < b[j]){
            v[i+j] = a[i];
            i++;
        }else{
            v[i+j] = b[j];
            j++;
        }
    }
    return ;
}

int main()
{
    f>>N>>A>>B>>C;
    int last = B;
    v.push_back(last);
    for(int i=2;i<=N;i++){
        last = (int)(((long long) A * (long long)last + (long long)B) % (long long)C);
        v.push_back(last);
    }
    quick_sort(v);
    for(int i=0;i<v.size();i+=10)
        g<<v[i]<<' ';
    return 0;
}