Cod sursa(job #212522)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 5 octombrie 2008 19:34:40
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
# include <cstdio>

using namespace std;

# define FIN "order.in"
# define FOUT "order.out"
# define MAXN 30000

int N,i,j,poz,a,b,c,l1,l2;
int A[3*MAXN];

    void build(int nod,int st,int dr)
    {
        int mij;
        
        if (st == dr)
          A[nod] = 1;
        else
          {
             mij = (st + dr) >> 1;
             build(nod<<1,st,mij);
             build(nod<<1|1,mij+1,dr);
             A[nod] = A[nod<<1] + A[nod<<1|1];
          }
    }
    
    void query(int nod,int st,int dr)
    {
        int mij;
        
        if (a <= st && dr <= b)
          c += A[nod];
        else
          {
             mij = (st + dr) >> 1;
             if (a <= mij)
               query(nod<<1,st,mij);
             if (b > mij)
               query(nod<<1|1,mij+1,dr);
          }
          
    }
    
    void update(int nod,int st,int dr)
    {
        int mij;
        
        if (st == dr)
          {
             printf("%d ",st);
             poz = st;
             A[nod] = 0;
          }
        else
          {
             mij = (st + dr) >> 1;
             if (c <= A[nod<<1])
               update(nod<<1,st,mij);
             else
               {
                 c -= A[nod<<1];
                 update(nod<<1|1,mij+1,dr);
               }
             A[nod] = A[nod<<1] + A[nod<<1|1];
          }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d",&N);
        
        build(1,1,N);
        poz = 1;
        for (i = 1; i <= N; ++i)
          {
             c = 0; a = poz+1; b = N;
             query(1,1,N);
             l1 = c;
             
             c = 0; a = 1; b = poz;
             query(1,1,N);
             l2 = c;
             
             c = i;
             if (c > l1+l2)
               if (c % (l1+l2)) c -= i/(l1+l2)*(l1+l2);
                 else c = l1+l2;
             if (c <= l1)
               {
                  c += l2;
                  update(1,1,N);
               }
             else
               {
                  c -= l1;
                  update(1,1,N);
               }
          }
        
        return 0;
    }