Cod sursa(job #2947633)

Utilizator cezarTriscaVicolCezar Trisca Vicol 2 cezarTriscaVicol Data 26 noiembrie 2022 15:04:22
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 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 merge_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]);
    merge_sort(a);
    merge_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 ;
}

void quick_sort(int* v, int n){
    if(n <= 1) return;
    if(n == 2){
        if(v[1] < v[0])
            swap(v[0], v[1]);
        return ;
    }
    int pivot = v[0];
    int i = 0, j = n-1;
    while(i <= j){
        while(v[i] < pivot) i++;
        while(v[j] > pivot) j--;
        if(i <= j){
            if(i < j)
                swap(v[i], v[j]);
            i++; j--;
        }
    }
    if(i<n-1)
        quick_sort(v+i, n-i);
    if(j>0)
        quick_sort(v, j+1);
}

int main()
{
    f>>N>>A>>B>>C;
    int v[N]; v[0] = B;
    for(int i=1;i<N;i++)
        v[i] = (int)(((long long) A * (long long)v[i-1] + (long long)B) % (long long)C);
    quick_sort(v, N);
    for(int i=0;i<N;i+=10)
        g<<v[i]<<' ';
    return 0;
}