Cod sursa(job #2129333)

Utilizator patcasrarespatcas rares danut patcasrares Data 12 februarie 2018 19:00:14
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define DN 100005
#define x first
#define y second
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
int n,poz,val1,a[4*DN],s[4*DN],val2;
long long k,t,nr;
void update(int nod,int st,int dr)
{
    if(st==dr)
    {
        a[nod]=val1;
        s[nod]=val2;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(2*nod,st,mij);
    else
        update(2*nod+1,mij+1,dr);
    a[nod]=min(a[2*nod],a[2*nod+1]);
    s[nod]=s[2*nod]+s[2*nod+1];
}
void query(int nod,int st,int dr,int sum)
{
    if(sum>=t)
    {
        k-=sum;
        poz=a[nod];
        return;
    }
    int mij=(st+dr)/2;
    if(sum+s[2*nod]-1>=t)
        query(2*nod,st,mij,sum);
    else
        query(2*nod+1,mij+1,dr,sum+s[2*nod]);
}
int main()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        poz=i;
        val1=i;
        val2=1;
        update(1,1,n);
    }
    nr=n;
    for(int i=1;i<=n;i++)
    {
        t=k-((nr-1)*(nr-2))/2;
        query(1,1,n,0);
        fout<<poz<<' ';
        val1=(1<<28);
        val2=0;
        update(1,1,n);
        nr--;
    }
}