Pagini recente » Cod sursa (job #2573225) | Cod sursa (job #2954441) | Cod sursa (job #2313549) | Cod sursa (job #285057) | Cod sursa (job #853925)
Cod sursa(job #853925)
#include <fstream>
#include <cstdlib>
#include <math.h>
#define NMAX 30000
using namespace std;
int buckets[NMAX];
int size_bucket[NMAX];
int copii[NMAX];
int bucket_end[NMAX];
int nr_copii;
int main()
{
ifstream input("order.in");
ofstream output("order.out");
input >> nr_copii;
int rad = sqrt(nr_copii);
for (int i =0;i<nr_copii;i++)
{
copii[i] = 1;
buckets[ i / rad] ++;
size_bucket[i / rad] ++;
bucket_end[ i / rad] = i + 1;
}
int next = 1;
int start = 1;
int nr_buckets;
if ( nr_copii % rad == 0)
{
nr_buckets = nr_copii / rad;
}
else
{
nr_buckets = nr_copii / rad + 1;
}
int N = nr_copii;
while (nr_copii > 0)
{
int current_bucket = (next + 1) / rad;
int where = start;
if (where > nr_copii)
if (where % nr_copii != 0) where = (start % nr_copii);
else where = nr_copii;
if (where < 0 ) where += nr_copii;
while (next < bucket_end[current_bucket])
{
if (copii[next] != 0)
{
where--;
if (where <= 0)
{
break;
}
}
next++;
}
next %= N;
current_bucket++;
current_bucket %= nr_buckets;
while (where > buckets[current_bucket])
{
where -= buckets[current_bucket];
next += size_bucket[current_bucket];
next %= N;
current_bucket ++;
current_bucket %= nr_buckets;
}
if (where > 0)
{
while (next < bucket_end[current_bucket])
{
if (copii[next] != 0)
{
where--;
if (where <= 0) break;
}
next++;
}
}
next %= N;
nr_copii --;
copii[next] = 0;
buckets[next / rad] --;
output << next +1 << " ";
start ++;
}
return 0;
}