Cod sursa(job #1151437)

Utilizator vlady1997Vlad Bucur vlady1997 Data 24 martie 2014 09:45:07
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
        #include <cstdio>
        #define zero(x) (x&(-x))
        using namespace std;
        int a[30001], s[30001], n;
        void update(int poz, int val)
        {
            for(int i=poz; i<=n; i+=zero(i)) a[i]+=val;
        }
        int query(int poz)
        {
            int i, r=0;
            for(i=poz; i>=1; i-=zero(i)) r+=a[i];
            return r;
        }
        int cb (int x)
        {
            int st,dr,m,s,Min=30010;
            st=1; dr=n;
            while(st<=dr)
            {
                m=(st+dr)/2;
                s=query(m);
                if(s==x && m<Min) Min=m;
                else if(s==x) dr=m-1;
                else if(s>x) dr=m-1;
                else st=m+1;
            }
            return Min;
        }
        int main()
        {
            int i, nr=0;
            freopen("order.in","r",stdin);
            freopen("order.out","w",stdout);
            scanf("%d",&n); int p=2, m=n-1;
            for (i=1; i<=n; i++) update(i,1);
            for (i=1; i<=n; i++)
            {
                int x=cb(p);
                update(x,-1);
                s[++nr]=x; p+=i;
                if (i!=n) p%=m;
                if (p==0) p=m; m--;
            }
            for (i=1; i<=n; i++) printf("%d ",s[i]);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }