Cod sursa(job #2916246)

Utilizator mihnea.cazan15mihnea cazan mihnea.cazan15 Data 28 iulie 2022 17:03:04
Problema Farfurii Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("farfurii.in");
ofstream out("farfurii.out");
int t[400005];
set<int> s;
void update(int nod,int l,int r,int poz,int val)
{
    if(l==r)
        {
            t[nod]+=val;
            return;
        }
    int m=(l+r)/2;
    if(poz<=m)
       update(2*nod,l,m,poz,val);
    else
        update(2*nod+1,m+1,r,poz,val);
    t[nod]=t[2*nod]+t[2*nod+1];
}
int query(int nod,int l,int r,int a,int b)
{
    if(a<=l && r<=b)
      return t[nod];
    int m=(l+r)/2,rl=0,rr=0;
    if(a<=m)
       rl=query(2*nod,l,m,a,b);
    if(m<b)
       rr=query(2*nod+1,m+1,r,a,b);
    return rl+rr;
}
int main()
{
    int n;
    ll k;
    in>>n>>k;
    for(int i=1;i<=n;i++)
        s.insert(i);
    for(int i=1;i<=n;i++)
    {
        auto val=s.begin();
        //out<<*val<<" ";
        while(val!=s.end())
        {
            //out<<*val<<" ";
            int p=*val-1-query(1,1,n,1,*val);
            if(p+(n-i-1)*(n-i)/2>=k)
            {
                out<<*val<<" ";
                //out<<*val-1-query(1,1,n,1,*val)<<"\n";
                k-=p;
                update(1,1,n,*val,1);
                s.erase(*val);
                break;
            }
            val++;
        }
        //out<<"\n";
    }
    return 0;
}