Cod sursa(job #2947653)

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

using namespace std;

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

void rearrange(int* v, int N, int val){
    stack<int> zeros, ones;
    for(int i=0;i<N;i++)
        if((v[i]/val)%2 == 0){
            zeros.push(v[i]);
        }else{
            ones.push(v[i]);
        }
    for(int i=N-1;i>=0;i--)
        if(!ones.empty()){
            v[i] = ones.top();
            ones.pop();
        }else{
            v[i] = zeros.top();
            zeros.pop();
        }
    return;
}

void radix_sort(int* v, int N){
    int val = 1;
    for(int i=0;i<31;i++){
        rearrange(v, N, val);
        if(i!=30)
            val*=2;
    }
}

int main()
{
    int N,A,B,C;
    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);
    radix_sort(v, N);
    for(int i=0;i<N;i+=10)
        g<<v[i]<<' ';
    return 0;
}