Cod sursa(job #1409609)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 30 martie 2015 16:55:41
Problema Nums Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("nums.in");
ofstream g("nums.out");

struct trie
{ short val;
  trie* fiu[10];
   trie()
  { val=0;
   for(int i=0;i<=9;i++)
    fiu[i]=NULL;
  }
};

 trie *el,*depth[100005];

 int n,lenact,len,use[100005]; char sir[100005];

void Add(char s[])
{ int i,len=strlen(s);
   use[len]++; lenact=max(lenact,len);
  el=depth[len];
   (el->val)++;


 for(i=0;i<len;i++)
 { if (el->fiu[s[i]-48]==NULL) el->fiu[s[i]-48]=new trie;
   el=el->fiu[s[i]-48];
    (el->val)++;
 }

}

void Query(int k)
{ int res=0,i,j,num;

   for(i=1;i<=lenact;i++)
    if (use[i]>=k) {res=i; break;}
     else k-=use[i];

el=depth[res];

  for(i=1;i<=res;i++)
  { for(j=0;j<=9;j++)
      if (el->fiu[j]!=NULL)
      { num=el->fiu[j]->val;
        if (num>=k) {g<<j; el=el->fiu[j]; break;}
         else k-=num;
      }
  }

 g<<"\n";
}

int main()
{ int i,t,k;


    f>>n;

   for(i=1;i<=100000;i++)
    depth[i]=new trie;

  for(i=1;i<=n;i++)
  { f>>t;

     if (!t) {f>>k; Query(k);}
      else {f>>sir; Add(sir);}

  }


    return 0;
}