Cod sursa(job #2442249)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 23 iulie 2019 14:25:38
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>

using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int nr,n,nrcp,aib[30005],poz,v[30005],nrx;
int ub(int x)
{
    return (x&(-x));
}
void Add(int x, int val)
{
    for(int i=x; i<=n; i+=ub(i))
        aib[i]+=val;
}
int sum(int x)
{
    int s=0;
    for(int i=x; i>=1; i-=ub(i))
        s+=aib[i];
    return s;
}
int caz2(int nr, int n, int poz)
{
    int st=1;
    int dr=poz;
    int mij=0;
    int p=0;
    int val=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        val=sum(mij);
        if(nr>val)
            st=mij+1;
        else
        {
            dr=mij-1;
            if(v[mij]==0)
                p=mij;
        }
    }
    return p;
}
int caz1(int nr, int n, int poz)
{
    int st=poz, dr=n, mij=0, p=0, val=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        val=sum(mij);
        if(nr>val)
            st=mij+1;
        else
        {
            dr=mij-1;
            if(v[mij]==0)
                p=mij;
        }
    }
    return p;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        Add(i,1);
    poz=2;
    Add(2,-1);
    v[2]=1;
    nrx=2;
    g<<2<<' ';
    nrcp=n-1;
    while(nrcp!=0)
    {
        nr=(nrx-1)%nrcp+1;
        if(sum(n)-sum(poz)<nr)
            poz=caz2(nr-(sum(n)-sum(poz)),n,poz);
        else
            poz=caz1(nr+sum(poz),n,poz);
        Add(poz,-1);
        v[poz]=1;
        nrcp--;
        nrx++;
        g<<poz<<' ';
    }
    return 0;
}