Cod sursa(job #1470683)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 11 august 2015 21:23:49
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (ll a=b;a<=c; ++a)
#define ROF(a,b,c) for (ll a=b;a>=c; --a)

using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
ll N,K;
int arb[262150];
// rezolvare folosind arbori de intervale
inline ll inversiuni(ll);
int query(int,int,int,int);
void update(int,int,int,int,int);

int main()
{
    f>>N>>K;
    FOR (i,1,N) {
        update(1,1,N,i,1);
    }
    ll left=1,right=N;
    while (left<right) { // caut binar pozitia de unde vectorul va incepe sa fie modificat
        int mij=(left+right)>>1;
        if (inversiuni(mij)<K) {
            right=mij-1;
        }
        else if (inversiuni(mij)==K) {
            left=mij;
            break;
        }
        else {
            left=mij+1;
        }
    }
    if (inversiuni(left)<K) {
        --left;
    }
    FOR (i,1,left-1) { // elementele din stanga acestei pozitii nu se vor schimba si sunt afisate si eliminate din pozitiile disponibile
        g<<i<<' ';
        ll poz=query(1,1,N,1);
        update(1,1,N,poz,-1);
    }
    int i=left;
    while (i<=N) { // se determina la fiecare pas farfuria de pe pozitia i
        ll inver=inversiuni(i+1);
        ll nr=K-inver;
        int poz=query(1,1,N,nr+1);
        g<<poz<<' ';
        update(1,1,N,poz,-1);
        K-=nr;
        ++i;
    }
    f.close();g.close();
    return 0;
}

inline ll inversiuni(ll x) { // calculez numarul maxim de inversiuni de la dreapta lui x
    ll nr=N-x+1;
    return nr*(nr-1)/2;
}

void update(int nod,int st,int dr,int poz,int val) { // adaug sau elimin o pozitie disponibila
    if (st==dr) {
        arb[nod]+=val;
    }
    else {
        ll mij=(st+dr)>>1;
        if (poz<=mij) {
            update((nod<<1),st,mij,poz,val);
        }
        else {
            update((nod<<1)+1,mij+1,dr,poz,val);
        }
        arb[nod]=arb[(nod<<1)]+arb[(nod<<1)+1];
    }
}

int query(int nod,int st,int dr,int poz) { // gasesc pe ce loc se afla a poz-a pozitie disponibila
    if (st==dr) {
        return st;
    }
    else {
        ll mij=(st+dr)>>1;
        if (arb[(nod<<1)]>=poz) {
            return query((nod<<1),st,mij,poz);
        }
        else {
            poz-=arb[(nod<<1)];
            return query((nod<<1)+1,mij+1,dr,poz);
        }
    }
}