Guest User

Untitled

a guest
Nov 6th, 2018
60
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. ll long_ceil(ll x, ll y)
  6. {
  7.     ll ans=x/y;
  8.     if(x%y!=0)
  9.         ans++;
  10.     return ans;
  11. }
  12.  
  13. int main()
  14. {
  15.     #ifndef ONLINE_JUDGE
  16.     freopen("input.txt", "r", stdin);
  17.     freopen("output.txt", "w", stdout);
  18.     #endif
  19.  
  20.     ios_base::sync_with_stdio(false);
  21.     ll i,j,fac[21];
  22.     fac[0]=1;
  23.     for(i=1;i<21;i++)
  24.         fac[i]=fac[i-1]*i;
  25.     ll k,q;
  26.     string str;
  27.     cin>>str>>q;
  28.     k=str.size();
  29.    
  30.     //only for testing purpose - not part of soln
  31.     set <char> s;
  32.     set <char>::iterator it;
  33.     for(i=0;i<k;i++) {
  34.         j=(ll)str[i];
  35.         assert(j>=97 && j<=122);
  36.         s.insert(str[i]);
  37.     }
  38.     ll k1=s.size(),f=0; //f- flag to check whether all characters are distinct
  39.     if(k==k1)
  40.         f=1;
  41.     assert(f==1);
  42.     assert(k>=1 && k<=20);
  43.     assert(q>=1 && q<=1000);
  44.     //testing part ends. solution continues.
  45.    
  46.     ll p[k+1],pc[k+1][k+1]; //p-permutation array; pc-precomp array
  47.     for(i=0;i<=k;i++) {
  48.         p[i]=fac[k]/fac[k-i];
  49.         for(j=0;j<=k;j++)
  50.             pc[i][j]=0;
  51.     }
  52.     for(i=1;i<=k;i++) {
  53.         for(j=i;j<=k;j++) {
  54.             if(i==1)
  55.                 pc[i][j]=p[j]/k;
  56.             else
  57.                 pc[i][j]=pc[i-1][j]/(k+1-i);
  58.         }
  59.     }
  60.     ll l[k+1]; //l-reqd. strings' Length determining array
  61.     l[0]=0; l[1]=pc[1][1];
  62.     for(i=2;i<=k;i++)
  63.         l[i]=l[i-1]+pc[1][i];
  64.     ll ts=l[k]*k; //ts-total no of all possible permutation of strings
  65.     while(q--) {
  66.         ll x,ct,t,t2,t3; //ct - length of expected string; t,...,t3 - tem variables
  67.         cin>>x;
  68.         assert(x>0); //queries tested.
  69.         if(x>ts) {
  70.             cout<<ts<<"\n";
  71.             continue;
  72.         }
  73.         set <char> s;
  74.         set <char>::iterator it;
  75.         for(i=0;i<k;i++)
  76.             s.insert(str[i]);
  77.  
  78.         string ans="";
  79.         char c;
  80.         t=long_ceil(x,l[k]);
  81.         x-=((t-1)*l[k]);
  82.         for(i=0;i<k;i++) {
  83.             if(x>l[i] && x<=l[i+1]) {
  84.                 break;
  85.             }
  86.         }
  87.         ct=t2=i+1;
  88.         it=s.begin();
  89.         for(i=1;i<t;i++)
  90.             it++;
  91.         c=(*it); ans+=c; ct--;
  92.         s.erase(it); x-=l[ct];
  93.         while(ct>0) {
  94.             t3=pc[t2+1-ct][t2];
  95.             t=long_ceil(x,t3);
  96.             it=s.begin();
  97.             for(i=1;i<t;i++)
  98.                 it++;
  99.             c=(*it); ans+=c; ct--;
  100.             s.erase(it); x-=((t-1)*t3);
  101.         }
  102.         cout<<ans<<"\n";
  103.     }
  104.     return 0;
  105. }
RAW Paste Data