Cod sursa(job #3260539)

Utilizator Stefanstef99Stefan Puica Stefanstef99 Data 2 decembrie 2024 17:59:33
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>
using namespace std;

/**

9
5 2 8 3 9 7 1 4 6
      1 2 3 4 5 6 7 8 9
fr  = 0 1 1 0 1 0 0 1 0
aib[i] = suma elementelor din fr[i-2^k+1,i] (de lungime 2^k)
         unde k este numarul de biti de 0 cu care se termina i
         in baza 2

i   baza_2  intervalul  suma
1   0001    [1,1]       0
2   0010    [1,2]       1
3   0011    [3,3]       1
4   0100    [1,4]       2
5   0101    [5,5]       1
6   0110    [5,6]       1
7   0111    [7,7]       0   [1,7] = [7,7]+[5,6]+[1,4]
8   1000    [1,8]       4
9   1001    [9,9]       0
*/

ifstream fin("schi.in");
ofstream fout("schi.out");
int aib[30002], n, sol[30002],a[30002];

/// ret. suma fr[1]+fr[2]+...+fr[p]
int Query(int p)
{
    int suma = 0;
    while (p > 0)
    {
        suma += aib[p];
        /// scadem din p valoarea 2^k
        p -= (p & (-p));
    }
    return suma;
}

/// aduna x la toate componentele aib[j] care-l contin pe p
void Update(int p, int x)
{
    while (p <= n)
    {
        aib[p] += x;
        p += (p & (-p));
    }
}

/// cauta cea mai din stanga poz p in care Query(p) = x
int CautBin(int x)
{
    int st,dr,mij,p,q;
    p=-1;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        q=Query(mij);
        if(q==x)
        {
            p=mij;
            dr=mij-1;
        }
        else if(q<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return p;
}

int main()
{
    int i, x, p;
    fin >> n;
    for (i = 1; i <= n; i++)
    {
        fin >> a[i];
        Update(i,1);
    }
    for(i=n;i>=1;i--)
    {
        x=a[i];
        /// cautam al x-lea 1
        p=CautBin(x);
        sol[p]=i;
        Update(p,-1);
    }
    for(i=1;i<=n;i++) fout<<sol[i]<<'\n';
    return 0;
}