Cod sursa(job #2410205)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 19 aprilie 2019 20:03:15
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>
#define ind(x) (x&(-x))

using namespace std;

ifstream f("order.in");
ofstream g("order.out");


int AIB[30100],n;

void adaug(int poz,int val)
{
    int i;
    for(i=poz;i<=n;i+=ind(i))
        AIB[i]+=val;
}

int suma(int poz)
{
    int i,S=0;
    for(i=poz;i>=1;i-=ind(i))
        S+=AIB[i];
    return S;
}


int i,p,u,pers,pers_ramase,mij,copie,poz_pe_care_sunt,numar_de_pers_ramase;

int main()
{

    f>>n;
    for(i=1;i<=n;i++)adaug(i,1);


    poz_pe_care_sunt=1;


    for(i=1;i<=n;i++)
    {


        numar_de_pers_ramase = suma(n)-suma(poz_pe_care_sunt);


        if(numar_de_pers_ramase>=i)
        {
            p=poz_pe_care_sunt;u=n;
            cout<<"DA";
            while(p<=u)
            {
                mij=(p+u)/2;
                pers = suma(mij)-suma(poz_pe_care_sunt);

                //cout<<mij<<" "<<pers<<'\n';

                if(pers>=i){copie=mij; u=mij-1;}
                else {p=mij+1;}
            }

            g<<copie<<" ";
            adaug(copie,-1);
            poz_pe_care_sunt=copie;
        }
        else
        {
            pers_ramase = i-numar_de_pers_ramase;

            pers_ramase = pers_ramase%suma(n);
            if(pers_ramase==0)pers_ramase=suma(n);

            p=1;u=n;


            while(p<=u)
            {
                mij=(p+u)/2;
                pers = suma(mij);

                if(pers>=pers_ramase){copie=mij; u=mij-1;}
                else {p=mij+1;}
            }

            g<<copie<<" ";
            adaug(copie,-1);
            poz_pe_care_sunt=copie;
        }

        cout<<'\n';

    }

    return 0;
}