Cod sursa(job #1676600)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 6 aprilie 2016 00:24:56
Problema Schi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<iterator>
#include<cmath>

using namespace std;

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

list <int> L[1000];
int n, nrad;
int V[30005], F[100];

void Read()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>V[i];
}

void Solve()
{
    int i, j, buc, pos;
    list <int>::iterator it;

    nrad = sqrt(n);
    for(i=1; i<nrad; i++)
        F[i] = nrad * i;
    F[nrad] = n;

    for(i=1; i<=n; i++){
        pos = V[i];
        for(j=1; j<=nrad && pos > F[j]; j++);
        buc = j;
        j = (j-1)*nrad + 1;
        if(L[buc].size() == 0){
            L[buc].push_front(i);
            continue;
        }
        for(it = L[buc].begin(); j < pos; it++, j++);
        L[buc].insert(it, i);
        while(L[buc].size() > nrad && buc != nrad){
            L[buc+1].push_front(L[buc].back());
            L[buc].pop_back();
            buc++;
        }
    }
}

void Print()
{
    int i;
    list <int>::iterator it;

    for(i=1; i<=nrad; i++)
        for(it = L[i].begin(); it != L[i].end(); it++)
            g<<*it<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}