Cod sursa(job #2944209)

Utilizator alexddAlexandru Dima alexdd Data 22 noiembrie 2022 10:42:19
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 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-i;
        cur++;
        if(cur>n)
            cur-=n;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(verif(cur,mij)>=i%(n-i+1))
            {
                if(mij==0 || verif(cur,mij-1)<i%(n-i+1))
                    break;
                else
                    dr=mij-1;
            }
            else
                st=mij+1;
        }
        int sf=cur+mij;
        if(sf>n)
            sf-=n;
        //fout<<cur<<" "<<sf<<"   "<<mij<<"\n";
        cur=sf;
        upd(cur,-1);
        fout<<cur<<" ";
    }

    return 0;
}
/**

1 2 3
  2
    3
1

*/