Cod sursa(job #1337109)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 8 februarie 2015 16:40:27
Problema Order Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 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],tot;
char s[nmax*5];
int st;

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);
}
void pune (int r)
{
    int q[6]={0};
    int i=0;
    while (r!=0) {
        q[++i]=r%10;
        r/=10;
    }
    for (int j=i;j>=1;j--) s[st++]=q[j]+'0';
    s[st++]=' ';
}
int main()
{
    int i,j,mut;
    int st,dr,mid,r;
    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) mut+=(n-i+1);
            sol=-1;
            r=ver(poz+1,n);
            if (mut<=r) {
                    st=poz;
                    dr=n;
                    while (st<=dr) {
                            mid=(st+dr)>>1;
                            if (ver(poz+1,mid)>=mut) {
                                    sol=mid;
                                    dr=mid-1;
                            } else {
                            st=mid+1;
                            }
                    }
            }
                else {
                    mut-=r;
                    st=1;
                    dr=poz-1;
                    while (st<=dr) {
                        mid=(st+dr)>>1;
                        if (ver(1,mid)>=mut) {
                                    sol=mid;
                                    dr=mid-1;
                        } else
                            st=mid+1;

                         }
            }

            pune(sol);
            v[sol]=0;
            poz=sol;
            x=0;
            update(1,1,n);
    }
    g<<s;
    return 0;
}