Cod sursa(job #1677556)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 6 aprilie 2016 17:35:25
Problema Schi Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<iterator>
#include<cmath>

using namespace std;

ofstream g("schi.out");

list <int> L[200];
int n, nrad, pos;
int V[30005], F[100];
char Buffer[10000];
int const Buffer_Size = 10000;

void read(int & nr)
{
    nr = 0;
    while((Buffer[pos] < '0' || Buffer[pos] > '9') && Buffer[pos]!='-'){
        pos++;
        if(pos == Buffer_Size){
            fread(Buffer, 1, Buffer_Size, stdin);
            pos = 0;
        }
    }

    while(Buffer[pos] >= '0' && Buffer[pos] <= '9'){
        nr = nr*10 + Buffer[pos++] - '0';
        if(pos == Buffer_Size){
            fread(Buffer, 1, Buffer_Size, stdin);
            pos = 0;
        }
    }
}

void Read()
{
    freopen("schi.in", "r", stdin);
    fread(Buffer, 1, Buffer_Size, stdin);

    read(n);
}

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++){
        read(pos);
        for(j=1; j<=nrad && pos > F[j]; j++);
        buc = j;
        j = (j-1)*nrad + 1;

        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;
}