SHARE
TWEET

2.B

a guest May 23rd, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. using namespace std;
  5. const int MAXN = 40000;
  6. int n;
  7. string s;
  8.  
  9. struct node {
  10.     int l, r, par, link;
  11.     map<char, int> next;
  12.     node()
  13.     {
  14.         l = 0;
  15.         r = 0;
  16.         par = -1;
  17.         link = -1;
  18.         next.clear();
  19.     }
  20.     node(int l_, int r_, int par_)
  21.     {
  22.         l = l_;
  23.         r = r_;
  24.         par = par_;
  25.         link = -1;
  26.         next.clear();
  27.     }
  28.     int len()
  29.     {
  30.         return r - l;
  31.     }
  32.     int &get(char c)        // кь амцаочшчек дмъпян и ыпмх неоекеллмх бпмюь уцале келзпщ
  33.     {
  34.         if(!next.count(c))
  35.         {
  36.             next[c] = -1;
  37.         }
  38.         return next[c];
  39.     }
  40. };
  41.  
  42. vector<node> t(MAXN);
  43. int sz;
  44.  
  45. struct state{           // нмймтелуе - аеоэ у нмцуфуз а оеюое и ноедия
  46.     int v, pos;
  47.     state(int v_, int pos_)
  48.     {
  49.         v = v_;
  50.         pos = pos_;
  51.     }
  52. };
  53.  
  54. state ptr (0, 0); // аъпчйу а имоелщ
  55.  
  56. state go(state st, int l, int r)        // смпук номесчпщ анеоед ъпомия s[l, r)
  57. {
  58.     while(l < r)
  59.     {
  60.         if(st.pos == t[st.v].len()) //неоехпу а ъй аеоэ еъйу кь ъпмук а имлфе оеюоч, а аеоэ ъммпа неоесмдя нм s[l]
  61.         {
  62.             st = state(t[st.v].get(s[l]), 0);
  63.             if(st.v == -1)
  64.             {
  65.                 return st;
  66.             }
  67.         }
  68.         else
  69.         {
  70.             if(s[t[st.v].l + st.pos] != s[l])    // ъй ъукамй дмйтел юьпщ s[l]
  71.             {
  72.                 return state(-1, -1);
  73.             }
  74.             if(r - l < t[st.v].len() - st.pos)      // еъйу кмтлм ъочця номхпу анеоед дм имлфч пм удек (нм удее кмтеп юьпщ леаеолм)
  75.             {
  76.                 return state(st.v, st.pos + r - l);
  77.             }
  78.             l += t[st.v].len() - st.pos;
  79.             st.pos = t[st.v].len();
  80.         }
  81.     }
  82.     return st;
  83. }
  84.  
  85. int split(state st)     //  а пеияшек нмймтелуу оетек у амцаочшчек лмаяв аеоэуля
  86. {
  87.     if(t[st.v].len() == st.pos)
  88.     {
  89.         return st.v;
  90.     }
  91.     if(st.pos == 0)
  92.     {
  93.         return t[st.v].par;
  94.     }
  95.     node v = t[st.v];
  96.     int id = sz++;          // ъмцдчйу лмаяв аеоэуля а ъеоедуле оеюоч, пенеощ келзек 4 ъъьйиу, мдлч яте еъпщ
  97.     t[id] = node(v.l, v.l + st.pos, v.par);
  98.     t[v.par].get( s[v.l] ) = id;
  99.     t[id].get(s[v.l + st.pos]) = st.v;
  100.     t[st.v].par = id;
  101.     t[st.v].l += st.pos;
  102.     return id;
  103. }
  104.  
  105. int get_link(int v)
  106. {
  107.     if(t[v].link != -1)
  108.     {
  109.         return t[v].link;
  110.     }
  111.     if(t[v].par == -1)
  112.     {
  113.         return 0;
  114.     }
  115.     int to = get_link(t[v].par);
  116.     return t[v].link = split(go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));
  117.     // удек мп ъярр ъъьйиу мп ноедич анеоед ъимйщим лчдм нм оеюоя у ле цчюьачек якелщэупщ дйуля лч 1 ълуця еъйу лчэ ноедми - имоелщ
  118.     // дмючаич 1                                                                ||||
  119. }
  120.  
  121. void tree_extend(int pos)
  122. {
  123.     while(true)
  124.     {
  125.         state nptr = go(ptr, pos, pos + 1);
  126.         if(nptr.v != -1)      // еъйу ъочця нмйябуймъщ номхпу - пм ми
  127.         {
  128.             ptr = nptr;
  129.             return;
  130.         }
  131.         int mid = split(ptr);
  132.         int leaf = sz++;
  133.         t[leaf] = node(pos, n, mid);
  134.         t[mid].get(s[pos]) = leaf;
  135.  
  136.         ptr.v = get_link(mid);      // смпук дчйщэе номъкчпоуачпщ аъе ъярруиъь у номдйуачпщ ус лч ъукамй, нмич ле ноудек а имоелщ
  137.         //йуюм нмич ъярруиъ анеоаье ле номдмйтупъз ъчк
  138.         ptr.pos = t[ptr.v].len();
  139.         if(!mid)
  140.         {
  141.             break;
  142.         }
  143.     }
  144. }
  145. void build_tree()
  146. {
  147.     sz = 1;
  148.     for(int i = 0; i < n; i++)
  149.     {
  150.         tree_extend(i);
  151.     }
  152. }
  153. void read(vector<ll> &a)
  154. {
  155.     for(int i = 0; i < a.size(); i++)
  156.     {
  157.         cin >> a[i];
  158.     }
  159. }
  160. vector<ll> d(MAXN, 0), baks(MAXN, 0), dist(MAXN, 0);
  161. void dfs(int v, char c, int dst)
  162. {
  163.     d[v] = 0;
  164.     baks[v] = 0;
  165.     ll ans = t[v].len();
  166.     if(t[v].next.size() == 0)
  167.     {
  168.         baks[v] = 1;
  169.     }
  170.     dist[v] = dst;
  171.     for(auto& item : t[v].next)
  172.     {
  173.         //cout << "HEHE";
  174.         //cout << item.first << ' ' << item.second << ' ' << "NOMER" << ' ';
  175.         dfs(item.second, item.first, dst + t[item.second].len());
  176.         d[v] += d[item.second];
  177.         baks[v] += baks[item.second];
  178.     }
  179.     d[v] += (dist[v] - ans) * ans * baks[v] + (ans + 1) * ans / 2 * baks[v];
  180.     if(t[v].next.size() == 0)
  181.     {
  182.         //cout << "LST" << ' ' << d[v] << endl;
  183.         d[v] -= (t[v].next.size() == 0) * dist[v];
  184.         //cout << endl << "GEG" << endl;
  185.     }
  186.     //cout << endl << v << ' ' << dist[v] << ' ' << c << ' ' << d[v] << ' ' << t[v].len() << ' ' << baks[v] << endl;
  187. }
  188. char fnd(int v, ll col)
  189. {
  190.     int ans = t[v].len();
  191.     ll cur = (dist[v] - ans) * ans * baks[v] + (ans + 1) * ans / 2 * baks[v] - (t[v].next.size() == 0) * dist[v];
  192.     //cout << "LMAO" << ' ' << v << ' ' << col << ' ' << cur << endl;
  193.     /*if(t[v].next.size() == 0)
  194.     {
  195.         return s[t[v].l + col - 1];
  196.     }*/
  197.  
  198.     //int cur = (dist[v] - ans) * ans * baks[v] + (ans + 1) * ans / 2 * baks[v] - (t[v].next.size() == 0) * dist[v];
  199.     if(col <= cur)
  200.     {
  201.         //cout << "PEK";
  202.         for(int i = 0; i < t[v].len(); i++)
  203.         {
  204.           //  cout << "EPT";
  205.             if(col <= (dist[v] - ans + i + 1) * baks[v])
  206.             {
  207.                 return s[t[v].l - (dist[v] - ans) + ((col) % (dist[v] - ans + i + 1) - 1 + (dist[v] - ans + i + 1)) % (dist[v] - ans + i + 1) ];
  208.             }
  209.             col -= (dist[v] - ans + i + 1) * baks[v];
  210.         }
  211.     }
  212.     //cout << "HEG";
  213.     col -= cur;
  214.     for(auto& item : t[v].next)
  215.     {
  216.         if(d[item.second] >= col)
  217.         {
  218.             //cout << "EBID";
  219.             return fnd(item.second, col);
  220.         }
  221.         col -= d[item.second];
  222.     }
  223.     return 'h';
  224. }
  225. void write(int v)
  226. {
  227.     cout << v << "  ";
  228.     for(auto& item : t[v].next)
  229.     {
  230.         cout << item.first << ' ' << item.second << ' ';
  231.     }
  232.     cout << endl;
  233.     for(auto& item : t[v].next)
  234.     {
  235.         write(item.second);
  236.     }
  237. }
  238. int main ()
  239. {
  240.  
  241.     //freopen("in.txt", "r", stdin);
  242.     //freopen("out.txt", "w", stdout);
  243.     ios::sync_with_stdio(0);cin.tie(0);
  244.     int m;
  245.     int ind = 1;
  246.     while(cin >> m)
  247.     {
  248.         if(m == 0)
  249.         {
  250.             return 0;
  251.         }
  252.         s.clear();
  253.         cin >> s;
  254.         //cout << s;
  255.         ptr = state(0, 0);
  256.         s += '$';
  257.         n = s.size();
  258.         t.assign(MAXN, node());
  259.         d.clear();
  260.         baks.assign(0, MAXN);
  261.         dist.clear();
  262.         //t.resize(MAXN);
  263.  
  264.         build_tree();
  265.         //write(0);
  266.         //cout << sz << endl;
  267.         vector<ll> a(m);
  268.         read(a);
  269.         dfs(0, '1', 0);
  270.         cout << "Case #";
  271.         cout << ind << ": ";
  272.         ind++;
  273.         for(int i = 0; i < m; i++)
  274.         {
  275.             //cout << "DHDHD";
  276.             cout << fnd(0, a[i]);
  277.         }
  278.         cout << endl;
  279.         //cout << d[min(3, sz - 1)] << endl;
  280.     }
  281.  
  282. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top