Pagini recente » Cod sursa (job #2802828) | Cod sursa (job #1831213) | Cod sursa (job #935673) | Cod sursa (job #923269) | Cod sursa (job #1495199)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = (int) 1e6;
const int Kmax = 20;
const int Mask = 255;
const int THRESHOLD = 100;
int v[Kmax * Nmax];
void insertionSort(int lo, int hi)
{
for ( int i = lo + 1; i < hi; i++ )
{
int x = v[i];
int j = i;
while ( j > lo && x < v[j - 1] )
{
v[j] = v[j - 1];
j--;
}
v[j] = x;
}
}
void radixPass(int lo, int hi, int bits)
{
int start[Mask + 1], finish[Mask + 1];
memset ( finish, 0, sizeof( finish ) );
for ( int i = lo; i < hi; i++ )
finish[ (v[i] >> bits) & Mask ]++;
start[0] = lo;
finish[0] += lo;
for ( int i = 1; i <= Mask; i++ )
{
start[i] = finish[i - 1];
finish[i] += finish[i - 1];
}
for ( int i = 0; i <= Mask; i++ )
{
while ( start[i] != finish[i] )
{
int elem = v[start[i]];
int bucket = ( elem >> bits ) & Mask;
while ( bucket != i )
{
int tmp = v[ start[bucket] ];
v[ start[bucket]++ ] = elem;
elem = tmp;
bucket = ( elem >> bits ) & Mask;
}
v[ start[i]++ ] = elem;
}
}
if ( bits )
{
for ( int i = 0; i <= Mask; i++ )
{
int siz = finish[i] - ( i ? finish[i - 1] : lo );
if ( siz > THRESHOLD )
radixPass( finish[i] - siz, finish[i], bits - 8 );
else if ( siz > 1 )
insertionSort( finish[i] - siz, finish[i] );
}
}
}
int main()
{
ifstream in("interclasari.in");
ofstream out("interclasari.out");
int k;
int n, sum = 0;
in >> k;
for ( int i = 0; i < k; i++ )
{
in >> n;
for ( int j = 0; j < n; j++ )
in >> v[sum + j];
sum += n;
}
in.close();
radixPass(0, sum, 24);
out << sum << '\n';
for ( int i = 0; i < sum; i++ )
out << v[i] << ' ';
out.close();
return 0;
}