Pagini recente » Cod sursa (job #3142343) | Cod sursa (job #2558564) | Cod sursa (job #1444709) | Cod sursa (job #2022499) | Cod sursa (job #2086804)
///arb tine cate elemente sunt folosite pe fiecare interval
#include <bits/stdc++.h>
using namespace std;
long long n,i,arb[300010],poz,k;
ofstream g ("farfurii.out");
void update(int node,int l,int r,long long lib)
{
if(l==r)
{
arb[node]=1;
g<<l<<" ";
return ;
}
int mid=(l+r)/2;
if(lib<=(mid-l+1)-arb[node*2])update(node*2,l,mid,lib);///daca avem suficiente libere pe intervalul l->mid,cautam al lib-lea nr nefolosit in intervalul l->mid
else update(node*2+1,mid+1,r,lib-((mid-l+1)-arb[node*2]));///daca sunt prea putine, cautam in mid+1->r
arb[node]=arb[node*2]+arb[node*2+1];
}
int main()
{
ifstream cin ("farfurii.in");
cin>>n>>k;
for(i=1; i<=n; ++i)
if(k<=(n-i)*(n-i-1)/2)update(1,1,n,1);///verificam daca putem pune el minim nefolosit(vom avea pe cele n-i pozitii ramase maxim (n-i)*(n-i-1)/2 inversiuni
else
{
///daca nu putem vrem sa ramanem cu nr maxim de inversiuni pe ultimele n-i pozitii ca valoare pt k
k=(n-i)*(n-i-1)/2;
///deci va trebui ca nr de pe poz i sa faca k-(n-i)*(n-i-1)/2 inversiuni, deci va trebui sa gasim al k-(n-i)*(n-i-1)/2+1 lea nr nefolosit
poz=k-(n-i)*(n-i-1)/2+1;
update(1,1,n,poz);
}
return 0;
}