Cod sursa(job #883732)

Utilizator maritimCristian Lambru maritim Data 20 februarie 2013 12:17:42
Problema NextSeq Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

FILE *f = fopen("nextseq.in","r");
FILE *g = fopen("nextseq.out","w");

typedef vector<pair<int,int> >::iterator it;

#define MaxN 10010
#define MH 666013

int N,M,P,Sol;
int A[MaxN],B[MaxN],C[MaxN];
vector<pair<int,int> > Hash[MH];

void citire(void)
{
    fscanf(f,"%d %d %d",&N,&M,&P);
    
    for(int i=1;i<=N;i++)
        fscanf(f,"%d ",&A[i]);
    for(int i=1;i<=M;i++)
        fscanf(f,"%d ",&B[i]);
    for(int i=1;i<=P;i++)
        fscanf(f,"%d ",&C[i]);
}

inline void addHash(int a,int poz)
{
    Hash[a%MH].push_back(make_pair(a,poz));
}

inline int takeHash(int a)
{
    int x = a%MH;

    for(it i=Hash[x].begin();i<Hash[x].end();i++)
        if(i->first == a)
            return i->second;

    return -1;
}

void creareHash(void)
{
    sort(A+1,A+N+1);

    for(int i=1;i<=N;i++)
        addHash(A[i],i-1);
}

inline void swap(int &a,int &b)
{
    int aux = a;
    a = b;
    b = aux;
}

void creareNumar(int N,int A[MaxN])
{
    for(int i=1;i<=N;i++)
        A[i] = takeHash(A[i]);

    for(int i=1;i<=N>>1;i++)
        swap(A[i],A[N-i+1]);

    A[0] = N;
}

inline int diferit(int A[MaxN],int B[MaxN])
{
    if(A[0] != B[0])
        return 1;

    for(int i=1;i<=A[0];i++)
        if(A[i] != B[i])
            return 1;

    return 0;
}

inline void aduna(int A[MaxN],int c)
{
    int aux = c;

    for(int i=1;i<=A[0];i++)
        aux = aux+A[i], A[i] = aux%N, aux /= N;

    for(;aux;aux /= N)
        ++ A[0];
}

inline void afisare(int A[MaxN])
{
    for(int i=A[0];i;i--)
        printf("%d ",A[i]);
    printf("\n");
}

void Rezolvare(void)
{
    creareHash();

    creareNumar(M,B);
    creareNumar(P,C);

//    afisare(B);

    for(Sol=0;diferit(B,C);Sol++)
        aduna(B,1);//,afisare(B);
}

int main()
{
    citire();
    Rezolvare();

    fprintf(g,"%d ",--Sol);
}