Cod sursa(job #2944622)

Utilizator alexddAlexandru Dima alexdd Data 22 noiembrie 2022 19:05:33
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n;
int aib[30001];
void upd(int poz, int val)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
        aib[i]+=val;
}
int qry(int poz)
{
    int rez=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        rez+=aib[i];
    return rez;
}
int query(int le, int ri)
{
    if(le>ri)
        return 0;
    return qry(ri)-qry(le-1);
}

int verif(int inc, int mutari)
{
    int sf;
    sf=inc+mutari;
    if(sf>n)
        sf-=n;
    if(sf==0)
        sf=n;
    if(inc<=sf)
        return query(inc,sf);
    else
        return query(1,sf)+query(inc,n);
}

int main()
{
    fin>>n;
    int cur=1;
    for(int i=1;i<=n;i++)
        upd(i,1);
    for(int i=1;i<=n;i++)
    {

        int st,dr,mij;
        st=0;
        dr=n;
        cur++;
        if(cur>n)
            cur-=n;
        int cate=i;
        while(cate>(n-i+1))
        {
            cate-=(n-i+1);
        }
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(verif(cur,mij)>=cate)
            {
                if(mij==0 || verif(cur,mij-1)<cate)
                    break;
                else
                    dr=mij-1;
            }
            else
                st=mij+1;
        }
        int sf=cur+mij;
        if(sf>n)
            sf-=n;
        cur=sf;
        upd(cur,-1);
        fout<<cur<<" ";
    }

    return 0;
}
/**

1 2 3  4
  2
    3
1
  2


*/