Cod sursa(job #853925)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 12 ianuarie 2013 16:03:34
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#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;
}