Cod sursa(job #2314281)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 8 ianuarie 2019 11:55:14
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <iostream>
#define si(nr) (nr&(-nr)) // si logic cu opusul unui numar
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
long long s,x;
int v[100001],aib[100001],N,K,r,pas,aux,index;
void adaugare(int p,int x)
{
    int i;
    for(i=p;i<=N;i+=si(i)) // i este incrementat cu pasul de si logic
    {
        aib[i]+=x;  // adaugarea lui x in arborele de interval
    }
}
void construire_v()//functia construieste vectorul v de dimensiune N
{
    int i;
    fin>>N>>K; //citim N-numarul de farfurii si K-numarul de tacamuri
    for(i=1;i<=N;i++)
    {
        s=N-i;
        x=(s*(s-1))/2; //x devine (s*(s-1))/2 deoarece K este marginit din restrictii de (N*(N-1))/2
        if(K>x)
        {
            v[i]=K-x; //v[i] devine K-x daca K>x
        }
        else
        {
            v[i]=0; //altfel K<=x si v[i] primeste 0
        }
        K-=v[i];
    }
}
int f(int r,int i)
{
    pas=(1<<16); //2 la puterea 16
    aux=0;
    while(pas!=0)
    {
        if(r+pas<=N)
        {
            index=r+pas; // in index calculam r-ul furnizat adunat cu pas daca este mai mic decat N-numarul de farfurii
            if(index+aux+aib[index]<v[i])// daca rezultatul calculat este mai mic decat elementul din v de la pozitia i
            {
                r+=pas;
                aux+=aib[index];
            }
        }
        pas=pas>>1; // pas descreste ca putere a lui 2
    }
    return r;
}
int main()
{
    int i;
    construire_v();//este construit vectorul v
    for(i=1;i<=N;i++)
    {
        v[i]++;//elementele sunt incrementate
        r=f(0,i); //calculam valoarea lui f pentru r=0 la pozitia i
        r++; //r este incrementam
        adaugare(r,-1); //il adaugam in arborele de intervale
        fout<<r<<" "; //afisam r
    }
    fin.close();
    fout.close();
    return 0;
}