Cod sursa(job #2610648)

Utilizator Rares31100Popa Rares Rares31100 Data 5 mai 2020 12:16:09
Problema Farfurii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 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;
}

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

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

    for(int i=1;i<=n;i++)
    {
        int toFind=min(n-i,K);
        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;
}