Cod sursa(job #1474915)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 23 august 2015 09:30:07
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.22 kb
#include <cstdio>

#define NMAX 100007
#define LL long long

using namespace std;
FILE *fin, *fout;
int n, check[NMAX], sol[NMAX], it;
LL k;

LL calc(int a)
{
    return (1LL * (n-a) * (n-a+1))/2;
}

void complet(int a)
{
    it = n;
    for(int i = a; i<= n; ++i)
    {
        while(check[it] == 1)
        {
            it--;
        }
        sol[i] = it;
        check[it] = 1;
    }
}
void solve()
{
    LL tmp;
    for(int i = 1; i<= n; ++i)
    {
        if(i == n)
        {
            sol[i] = n;
            check[n] = 1;
            continue;
        }
        tmp = calc(i+1);
        if(tmp > k)
        {
            sol[i] = i;
            check[i] = 1;
            continue;
        }
        if(tmp <= k)
        {
            sol[i] = i + k - tmp;
            check[i + k - tmp] = 1;
            complet(i+1);
            break;
        }
    }
}
void afisare()
{
    for(int i = 1; i<= n; ++i) printf("%d ", sol[i]);
    printf("\n");
}

int main()
{
    fin = freopen("farfurii.in", "r", stdin);
    fout = freopen("farfurii.out", "w", stdout);
    scanf("%d%lld", &n, &k);
    solve();
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}