Cod sursa(job #1151564)

Utilizator victor_crivatCrivat Victor victor_crivat Data 24 martie 2014 11:10:24
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#define soto(x) (x&(-x))
using namespace std;
int a[30001],b[30001],n,i,poz,aux,x;
void update(int poz, int val)
{
    for(int i=poz; i<=n; i+=soto(i)) a[i]+=val;
}
int query(int poz)
{
    int i, rip=0;
    for(i=poz; i>=1; i-=soto(i)) rip+=a[i];
    return rip;
}
int find(int x)
{
    int st,dr,m,s,mmin=1000000;
    st=1; dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        s=query(m);
        if(s==x && m<mmin) mmin=m;
        else if(s==x) dr=m-1;
        else if(s>x) dr=m-1;
        else st=m+1;
    }
    return mmin;
}
int main()
{
    ifstream f("order.in");
    ofstream g("order.out");
    f>>n;
    for (i=1; i<=n; i++)
        update (i,1);
    poz=2,aux=n-1;
    for (i=1; i<=n; i++)
    {
        x=find(poz);
        update(x,-1);
        g<<x<<" ";
        poz+=i;
        if(poz>aux && i!=n) poz%=aux;
        if(!poz && i!=n) poz=aux;
        aux--;
    }
f.close();
g.close();
return 0;
}