Pagini recente » Cod sursa (job #2552655) | Cod sursa (job #2363696) | Cod sursa (job #1942618) | Cod sursa (job #1152518) | Cod sursa (job #2314281)
#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;
}