Cod sursa(job #470555)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 14 iulie 2010 16:13:13
Problema Nums Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include<cstdio>
#include<cstring>
#define L 1<<17
int max,pc,pp,q;
int rasp[L];
struct Nod
{
    int nrcuv;
    Nod *f[10];
    Nod()
    {
        for(int i=0;i<10;i++)
            f[i]=NULL;
        nrcuv=0;
    }
};
void init()
{
    int poz,x,n,lung;
    char s[L];
    freopen("nums.in","r",stdin);
    freopen("nums.out","w",stdout);
    scanf("%d",&n);
    memset(s,L,'\x0');
    for(int i=1;i<=n;i++)
    {
        scanf("%d ",&x);
        memset(s,L,'\x0');
        if(x==1)
        {
            scanf("%s\n",&s);
            lung=strlen(s);
            if(lung>max)
                max=lung;
        }
        else scanf("%d",&poz);
    }
    fclose(stdin);
}
void insert(Nod *nod,char str[L],int lung,int poz)
{
    if(poz==lung)
    {
        ++nod->nrcuv;
        return;
    }
    if(pc+lung<max)
    {
        pc++;
        if(nod->f[0])
        {
            ++nod->nrcuv;
            insert(nod->f[0],str,lung,poz);
            return;
        }
        ++nod->nrcuv;
        nod->f[0]=new Nod();
        insert(nod->f[0],str,lung,poz);
        return;
    }
    int cor=str[poz]-'0';
    if(nod->f[cor])
    {
        ++nod->nrcuv;
        insert(nod->f[cor],str,lung,poz+1);
        return;
    }
    ++nod->nrcuv;
    nod->f[cor]=new Nod();
    insert(nod->f[cor],str,lung,poz+1);
}
void check(Nod *nod,int poz)
{
    for(int i=0;i<10;i++)
        if(nod->f[i])
        {
            if(pp+(nod->f[i]->nrcuv)<poz)
            {
                pp+=nod->f[i]->nrcuv;
                continue;
            }
            rasp[++q]=i;
            check(nod->f[i],poz);
            return;
        }
}
void read()
{
    int poz,x,n;
    char s[L];
    freopen("nums.in","r",stdin);
    scanf("%d",&n);
    memset(s,L,'\x0');
    Nod *first=new Nod();
    for(int i=1;i<=n;i++)
    {
        scanf("%d ",&x);
        memset(s,L,'\x0');
        if(x==1)
        {
            scanf("%s\n",&s);
            int lung=strlen(s);
            pc=0;
            insert(first,s,lung,0);
        }
        else
        {
            scanf("%d",&poz);
            pp=0;
            q=0;
            check(first,poz);
            bool ok=false;
            for(int j=1;j<=q;j++)
                if(ok==false && rasp[j])
                {
                    ok=true;
                    printf("%d",rasp[j]);
                }
                else if(ok==true)
                    printf("%d",rasp[j]);
            printf("\n");
        }
    }
    fclose(stdin);
}
int main()
{
    init();
    read();
    return 0;
}