Cod sursa(job #2438059)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 11 iulie 2019 10:17:48
Problema Order Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>
#define bits(i) (i&(-i))
using namespace std;

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

int n,AIB[30100];

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

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

int i,t,poz,p,u,mij,copii_ramasi,copii_de_eliminat,copiin,v[30100];
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        v[i]=i;
        adaug(i,1);
    }
    t=0;
    poz=1;

    while(t<n)
    {
        copii_de_eliminat=t+1;

        // Pot sa mai elimin pana in n
        copiin=suma(n)-suma(poz);

        if(copiin>=copii_de_eliminat)
        {
            p=poz;
            u=n;
            while(p<=u)
            {
                mij=(p+u)/2;
                if(suma(mij)-suma(poz)>copii_de_eliminat)u=mij-1;
                else if(suma(mij)-suma(poz)<copii_de_eliminat)p=mij+1;
                else {poz=mij;u=mij-1;}
            }
        }

        else
        {
            copii_de_eliminat-=copiin;
            // Cicluri de n
            copii_ramasi=suma(n);
            copii_de_eliminat=copii_de_eliminat%copii_ramasi;
            if(copii_de_eliminat==0)copii_de_eliminat=copii_ramasi;

            // De la 1 pana in n
            p=1;
            u=n;
            while(p<=u)
            {
                mij=(p+u)/2;
                if(suma(mij)>copii_de_eliminat)u=mij-1;
                else if(suma(mij)<copii_de_eliminat)p=mij+1;
                else {poz=mij;u=mij-1;}
            }

        }

        // Final
        adaug(poz,-1);
        g<<poz<<" ";
        t++;
    }
    return 0;
}