Cod sursa(job #1134422)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 6 martie 2014 15:16:56
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>


#define DN 100005
#define pb push_back
#define mp make_pair
#define per pair<int,int>
#define INF (1<<30)
#define LL long long
#define un unsigned
#define x first
#define y second
using namespace std;

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


int n,k,arb[4*DN],r,x;
LL S;

void build_arb(int nod,int left,int right){


    if(left==right){

        arb[nod] = 1;
        return;
    }
    int mij = (left+right)/2;

    build_arb(2*nod,left,mij);
    build_arb(2*nod+1,mij+1,right);

    arb[nod]=arb[2*nod] + arb[2*nod+1];
}
void fnd(int nod,int left,int right){

    if(left==right){

        k-=S;
        g<<left<<" ";
        arb[nod] = 0 ;/// folosesc nodul
        return;
    }
    int mij=(left+right)/2;

    if( S + arb[2*nod] - 1 + r*1ll*(r-1)/2 >=k && arb[2*nod]){
        fnd(2*nod,left,mij);
    }else{

        S+=arb[2*nod];
        fnd(2*nod+1,mij+1,right);
    }
    arb[nod]=arb[2*nod] + arb[2*nod+1];
}


int main()
{
    int p;
    f>>n>>k;

    build_arb(1,1,n);

    r = n,p = n;
    for(;p;--p){

        S=0;
        --r;
        fnd(1,1,n);
    }


    return 0;
}