Cod sursa(job #1810574)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 20 noiembrie 2016 11:09:07
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

using namespace std;
int n,i,j,k,w,r,p,in,q[30005],v[18][30005];
int cauta(int x)
{
    int poz;
    w=in;
    poz=1;
    while(w>0)
    {
        w--;
        if(v[w][2*poz-1]>=x) poz=2*poz-1;
        else
        {
            poz=2*poz;
            x-=v[w][poz-1];
        }
    }
    return poz;
}
void elimina(int poz)
{
    w=0;
    while(w<=in)
    {
        v[w][poz]--;
        w++;
        poz=(poz+1)/2;
    }
}
int main()
{
    ifstream f("order.in");
    ofstream g("order.out");
    f>>n;
    k=n;
    p=1;
    while(k>1)
    {
        for(j=1; j<=k; j++)
        v[in][j]=p;
        p*=2;
        in++;
        k=(k+1)/2;
    }
    v[in][1]=p;
    j=2;
    k=2;
    r=n;
    for(i=2; i<=n; i++)
    {
        q[i-1]=j;
        k--;
        elimina(j);
        r--;
        k+=i;
        k=(k-1)%r+1;
        j=(cauta(k)-1)%n+1;
    }
    for(i=1; i<n; i++) g<<q[i]<<" ";
    g<<j<<'\n';
    f.close(); g.close();
    return 0;
}