Cod sursa(job #292649)

Utilizator crawlerPuni Andrei Paul crawler Data 31 martie 2009 12:50:54
Problema NextSeq Scor 85
Compilator cpp Status done
Runda qwerty-6 Marime 2.25 kb
#include <stdio.h>
#include <string.h>

#define Nmax 10100

int a[Nmax];
int b[Nmax];
int v[Nmax];
int N,A,B;

int egal()
{
     if (a[0] != b[0])
          return 0;
     for (int i=1;i<=a[0];++i)
          if (a[i]!=b[i])
               return 0;
     return 1;     
}

void sort(int st,int dr)
{
     int i = st, j = dr;
     int tmp, sch = v[(i+j)/2];
     do
     {
          while (v[i] < sch) ++i;
          while (v[j] > sch) --j;
          if (i<=j)
          {
               tmp = v[i];
               v[i] = v[j];
               v[j] = tmp;
               ++i; --j;     
          }          
     } while (i<=j);
     if (st<j) sort(st,j);
     if (i<dr) sort(i,dr);     
}

int main()
{
     freopen("nextseq.in","r",stdin);
     freopen("nextseq.out","w",stdout);
     
     scanf("%d%d%d", &N, &A, &B);
     
     for (int i=1;i<=N;++i)
          scanf("%d", &v[i]);
     sort(1,N);

     a[0] = A;
     for (int i=1;i<=A;++i)
     {
          scanf("%d", &a[A-i+1]);
          int x=0;
          for (int k=1<<10;k>0;k/=2) if (x+k <= N)
               if (v[x+k] <= a[A-i+1])
                    x += k;
          a[A-i+1] = x;          
     }

     b[0] = B;
     for (int i=1;i<=B;++i)
     {
          scanf("%d", &b[B-i+1]);
          int x=0;
          for (int k=1<<10;k>0;k/=2) if (x+k <= N)
               if (v[x+k] <= b[B-i+1])
                    x += k;
          b[B-i+1] = x;
     }
          
     int ret = 0;
     int t;
/*
     for (int i=a[0];i>0;--i)
          printf("%d ", a[i]);
     printf("\n");
*/     
     while (!egal())
     {
          ++ret;
          t = 1;
          int i;
          for (i=1;i<=a[0];++i)
          {
               a[i] += t;
               if (a[i] > N)
               {
                    a[i] -= N;
                    t = 1;     
               }
                    else
               t = 0;
          }
               
          if (t)
               a[++a[0]] = 1;
          /*
          for (int i=a[0];i>0;--i)
               printf("%d ", a[i]);
          printf("\n");   
          */            
     }
     
     if (ret > 0)
          --ret;
     
     printf("%d\n", ret);
     
     return 0;     
}