Cod sursa(job #1337092)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 8 februarie 2015 16:26:53
Problema Order Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <fstream>
#define nmax 30005
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n,poz,x;
int adi[nmax*3],sol;
int v[nmax];

void update(int nod ,int st, int dr)
{
    if (st==dr) {
        adi[nod]=x;
        return;
    }
    int mid=(st+dr)>>1;

    if (poz<=mid) update(nod*2,st,mid);
    if (poz>mid) update(nod*2+1,mid+1,dr);

    adi[nod]=adi[nod*2]+adi[nod*2+1];
}
int query(int nod ,int st, int dr,int p1,int p2)
{
    if (p1<=st&&dr<=p2) {
            return adi[nod];
    }
    int mid=(st+dr)>>1;
    int x=0;

    if (p1<=mid) {
            x+=query(nod*2,st,mid,p1,p2);
    }
    if (p2>mid) {
            x+=query(nod*2+1,mid+1,dr,p1,p2);
    }
    return x;
}
int ver(int p1,int p2)
{
    if (p1!=1) return query(1,1,n,1,p2)-query(1,1,n,1,p1-1);
    return query(1,1,n,1,p2);
}

int main()
{
    int i,j,mut;
    int st,dr,mid;
    f>>n;
    for (i=1;i<=n;i++) {
        poz=i;
        x=1;
        update(1,1,n);
        v[i]=1;
    }
    poz=1;

    for (i=1;i<=n;i++) {
            mut=i;
            mut%=(n-i+1);
            if (mut==0) {

                while (poz>=1&&v[poz]==0) poz--;
                if (poz<1) {
                    poz=n;
                    while (v[poz]==0) poz--;
                }
                v[poz]=0;
                g<<poz<<' ';
                x=0;
                update(1,1,n);
                continue;
            }

            sol=-1;
            st=poz;
            dr=n;
            while (st<=dr) {
                    int mid=(st+dr)>>1;
                    if (ver(poz+1,mid)>=mut) {
                            sol=mid;
                            dr=mid-1;
                    } else {
                            st=mid+1;
                    }
            }
            mut-=ver(poz+1,n);

            if (mut>0) {st=1;
                         dr=poz-1;
                         while (st<=dr) {
                                int mid=(st+dr)>>1;
                                if (ver(1,mid)>=mut) {
                                            sol=mid;
                                            dr=mid-1;
                                } else {
                                        st=mid+1;
                                }
                         }
            }
            g<<sol<<' ';
            v[sol]=0;
            poz=sol;
            x=0;
            update(1,1,n);
    }

    return 0;
}