Cod sursa(job #2022954)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 17 septembrie 2017 20:08:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <stdlib.h>
#include <string.h>
#define nmax 30005
using namespace std;
fstream f1("schi.in", ios::in);
fstream f2("schi.out", ios::out);
int n, sol[nmax], q[nmax], aib[nmax];
///aib[x]= suma el de pe intervalul [x-2^k +1.. x] din vect initial 1 1 1 1 1 1 1 1
///cauti a q[i]-a valoare de 1 de la stanga la dreapta binar
///sum in aib de la 1 la mijl=q[i] si mijl minim
///aceasta e poz cautata
///apoi pui pe 0 pozitia q[i]
void adauga(int poz, int val)
{
    ///adaugi val la toate intervalele cu propr ca: au capat dr>=x si in contin pe x
    ///acestea sunt de la aib[x] , aib[x+2^k],... aib[valmax]
    while(poz<=n)
    {
        aib[poz]+=val;
        poz=2*poz-(poz&(poz-1));
    }
}
void citire()
{
    int i;
    f1>>n;
    for(i=1; i<=n; i++)
        {
            f1>>q[i];
            adauga(i, 1);
        }
}
void afis()
{
    int i;
    for(i=1; i<=n; i++)
        f2<<sol[i]<<"\n";
}
int sum(int poz) ///suma in aib de la poz 1 la poz
{
  int su=0;
  while(poz>0)
  {
      su+=aib[poz];
      poz=poz& (poz-1);
  }
  return su;
}
int cauta_in_sum(int st, int dr, int val)
{
    if(st<=dr)
    {
        int mijl=(st+dr)/2, x=sum(mijl);
        if((x==val)&&((mijl==1)||(sum(mijl-1)<val))) return mijl;
        else if(x<val) return cauta_in_sum(mijl+1, dr, val);
             else return cauta_in_sum(st, mijl-1, val);
    }
}
void solutie()
{
    int i, poz;
    for(i=n; i>=1; i--)
    {
        poz=cauta_in_sum(1, n, q[i]);
        sol[poz]=i;
        adauga(poz,  -1);
    }
}
int main()
{
    citire();
    solutie();
    afis();
    return 0;
}