Cod sursa(job #2146497)

Utilizator DanizisSpartanulDani Mocanu DanizisSpartanul Data 28 februarie 2018 00:07:47
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

const int NMax=15005;

class SegmentTree
{
    public:SegmentTree(int size)
    {
        N=size;
        int lg=ceil(log2(N));
        ST.resize(1<<lg+1);
    }
    public:void Insert(int index)
    {
        Insert(index,1,1,N);
    }
    public:void Query(int index)
    {
        Query(1,index,1,N);
    }


    private:int N;
    private:vector<int> ST;

    private:void Insert(int index,int node,int left,int right)
    {
        if(left==right)
        {
            ST[node]=1;
            return;
        }
        int middle=(left+right)/2;
        Insert(index,2*node,left,middle);
        Insert(index,2*node+1,middle+1,right);
        ST[node]+=ST[2*node]+ST[2*node+1];
    }

    private:void Query(int node,int index,int left, int right)
    {
        if(left==right)
        {
            ST[node]=0;
            fout<<left<<" ";
            return;
        }
        int middle=(left+right)/2;
        if(index<=ST[2*node])
            Query(2*node,index,left,middle);
        else
            Query(2*node+1,index-ST[2*node],middle+1,right);
        ST[node]=ST[2*node]+ST[2*node+1];
    }
};

int N,K;

int main()
{
    fin>>N>>K;
    SegmentTree segmentTree(N);
    segmentTree.Insert(1);
    for(int i=N-1;i>=0;i--)
        if(K<=i*(i-1)/2)
            segmentTree.Query(1);
        else
            segmentTree.Query(K-i*(i-1)/2+1), K=i*(i-1)/2;

    return 0;
}