Cod sursa(job #1334530)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 4 februarie 2015 14:19:21
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.56 kb
#include <stdio.h>
#define NMAX 150023
FILE *fin, *fout;
int n, arb[2*NMAX], v[NMAX];
long long int m;
inline void pun(int st, int dr, int pos, int nod)
{
    if(st == dr)
    {
        arb[nod] = 1;
        return;
    }
    int mij = (st+dr)/2;
    if(pos <= mij) pun(st, mij, pos, 2*nod);
    if(pos > mij) pun(mij+1, dr, pos, 2*nod+1);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
    return;
}
inline int interogare(int st, int dr, int st1, int dr1, int nod)
{
    if(st == st1 && dr == dr1)
    {
        return arb[nod];
    }
    int mij = (st+dr)/2;
    if(dr1 <= mij) return interogare(st, mij, st1, dr1, 2*nod);
    if(st1 > mij) return interogare(mij+1, dr, st1, dr1, 2*nod+1);
    return interogare(st, mij, st1, mij, 2*nod) + interogare(mij+1, dr, mij+1, dr1, 2*nod+1);
}
int main()
{
    fin = fopen("farfurii.in", "r");
    fout = fopen("farfurii.out", "w");
    fscanf(fin, "%d%lld", &n, &m);
    for(int i = 1; i<= n; i++)
    {
        if(m < 1LL*((n-i)*(n-i-1))/2)
        {
            v[i] = i;
            pun(1, n, i, 1);
        }
        else
        {
            int temp = (int)(m - 1LL*((n-i)*(n-i-1))/2 + 1), temp1;
            while(1)
            {
                temp1 = temp;
                temp = interogare(1, n, 1, temp, 1) + (int)(m - 1LL*((n-i)*(n-i-1))/2 + 1);
                if(temp == temp1) break;
            }
            v[i] = temp;
            pun(1, n, temp, 1);
            m=1LL*((n-i)*(n-i-1))/2;
        }
    }
    for(int i = 1; i<= n; i++) fprintf(fout, "%d ", v[i]);fprintf(fout, "\n");
    fclose(fin);
    fclose(fout);
    return 0;
}