Cod sursa(job #1470660)

Utilizator MaligMamaliga cu smantana Malig Data 11 august 2015 20:27:53
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 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 (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
int N,K,dimrez;
int aib[100010],rez[100010];

inline int inversiuni(int);
int query(int);
void update(int,int);
int binarysearch(int);

int main()
{
    f>>N>>K;
    FOR (i,1,N) {
        update(i,1);
    }
    int left=1,right=N;
    //cout<<inversiuni(2);
    while (left<right) {
        int mij=(left+right)>>1;
        //cout<<mij<<' '<<inversiuni(mij)<<'\n';
        if (inversiuni(mij)<K) {
            right=mij-1;
        }
        else if (inversiuni(mij)==K) {
            left=mij;
            break;
        }
        else {
            left=mij+1;
        }
    }
    if (inversiuni(left)<K) {
        --left;
    }
    //cout<<left<<'\n';
    FOR (i,1,left-1) {
        rez[++dimrez]=i;
        int poz=binarysearch(1);
        update(poz,-1);
    }
    //cout<<query(N)<<'\n';
    int i=left;
    while (i<=N) {
        int inver=inversiuni(i+1);
        int nr=K-inver;
        /*cout<<i<<' '<<K<<' '<<inver<<' '<<nr+1<<'\n';
        FOR(j,1,N) {
            cout<<j<<' '<<aib[j]<<'\n';
        }
        cout<<"\n";*/
        int poz=binarysearch(nr+1);
        rez[++dimrez]=poz;
        update(poz,-1);
        K-=nr;
        ++i;
    }
    if (dimrez<N) {
        int poz=binarysearch(1);
        rez[++dimrez]=poz;
        update(poz,-1);
    }
    FOR (i,1,dimrez) {
        g<<rez[i]<<' ';
    }
    f.close();g.close();
    return 0;
}

inline int inversiuni(int x) {
    int nr=N-x+1;
    return nr*(nr-1)/2;
}

void update(int poz,int val) {
    int C=0;
    while (poz<=N) {
        aib[poz]+=val;
        while (!(poz&(1<<C))) {
            ++C;
        }
        poz+=(1<<C);
        ++C;
    }
}

int query(int poz) {
    int S=0,C=0;
    while (poz) {
        S+=aib[poz];
        while (!(poz&(1<<C))) {
            ++C;
        }
        poz-=(1<<C);
        ++C;
    }
    return S;
}

int binarysearch(int poz) {
    int left=1,right=N;
    while (left<right) {
        int mij=(left+right)>>1;
        int val=query(mij);
        if (val>=poz) {
            right=mij;
        }
        else {
            left=mij+1;
        }
    }
    return left;
}