Cod sursa(job #2610669)

Utilizator Rares31100Popa Rares Rares31100 Data 5 mai 2020 12:45:56
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

long long n,K;
int perm[100001];
int arb[100001];

void add(int poz,int val)
{
    while(poz<=n)
    {
        arb[poz]+=val;
        poz+=poz&-poz;
    }
}

int sum(int poz)
{
    int s=0;

    while(poz)
    {
        s+=arb[poz];
        poz-=poz&-poz;
    }

    return s;
}

int findNr(int nr)
{
    int poz=n+1;
    for(int p=n;p;p/=2)
        while(poz-p>0 && sum(poz-p)>=nr)
            poz-=p;

    return poz;
}

long long gauss(long long x)
{
    return (x*(x+1))/2;
}

int main()
{
    in>>n>>K;

    for(int i=1;i<=n;i++)
        add(i,1);

    for(int i=1;i<=n;i++)
    {
        int toFind;
        if( K > gauss(n-i-1) )
            toFind=K-gauss(n-i-1);
        else
            toFind=0;

        K-=toFind;

        int numar=findNr(toFind+1);
        add(numar,-1);

        perm[i]=numar;
    }

    for(int i=1;i<=n;i++)
        out<<perm[i]<<' ';

    return 0;
}