Pagini recente » Cod sursa (job #1821423) | Cod sursa (job #2797335) | Cod sursa (job #761882) | Cod sursa (job #5582) | Cod sursa (job #980099)
Cod sursa(job #980099)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define Nmax 500002
static const unsigned int digits = 2; //Digits
static const unsigned int r = 16; //Bits
static const unsigned int radix = 1 << r; //Bins
static const unsigned int mask = radix - 1;
void radix_sort(std::vector<int>& A){
const int n = A.size();
std::vector<unsigned int> B(n+1);
std::vector<unsigned int> cnt(radix);
for(unsigned int i = 0, shift = 0; i < digits; i++, shift += r){
for(unsigned int j = 0; j < radix; ++j){
cnt[j] = 0;
}
for(unsigned int j = 0; j < n; ++j){
++cnt[(A[j] >> shift) & mask];
}
for(unsigned int j = 1; j < radix; ++j){
cnt[j] += cnt[j - 1];
}
for(long j = n - 1; j >= 0; --j){
B[--cnt[(A[j] >> shift) & mask]] = A[j];
}
for(unsigned int j = 0; j < n; ++j){
A[j] = B[j];
}
}
}
int main()
{
ifstream f("sdo.in");
ofstream g("sdo.out");
int k, n;
f >> n >> k;
vector<int> A;
for ( int i = 0, a; i < n; i++ )
f >> a,
A.push_back( a );
radix_sort(A);
g << A[k-1];
return 0;
}