Cod sursa(job #2626387)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 6 iunie 2020 14:05:47
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#define MAX 30005
using namespace std;
int n,arb[MAX];
int nr(int x)
{
    return (x&-x);
}
void update(int poz,int val)
{
    while(poz<=n)
    {
        arb[poz]+=val;
        poz+=nr(poz);
    }
}
int query(int poz)
{
    int s=0,i;int k=0;
    for( i=(1<<15);i;i=(i>>1))
    {
        if(k+i<=n and s+arb[i+k]<poz)
        {
            s+=arb[i+k];
            k+=i;
        }
    }
    k++;
    return k;
}
int i,poz,val;
int main()
{
    ifstream fin("order.in");
    ofstream fout("order.out");
    fin>>n;
    for(i=1;i<=n;i++)
    {
        update(i,1);
    }
    poz=2;
    for(i=1;i<=n;i++)
    {
        poz=(poz-2+i)%(n-i+1)+1;
        val=query(poz);
        update(val,-1);
       fout<<val<<" ";
    }
    return 0;
}