Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll long long
- #define ld long double
- using namespace std;
- const int MAXN = 40000;
- int n;
- string s;
- struct node {
- int l, r, par, link;
- map<char, int> next;
- node()
- {
- l = 0;
- r = 0;
- par = -1;
- link = -1;
- next.clear();
- }
- node(int l_, int r_, int par_)
- {
- l = l_;
- r = r_;
- par = par_;
- link = -1;
- next.clear();
- }
- int len()
- {
- return r - l;
- }
- int &get(char c) // кь амцаочшчек дмъпян и ыпмх неоекеллмх бпмюь уцале келзпщ
- {
- if(!next.count(c))
- {
- next[c] = -1;
- }
- return next[c];
- }
- };
- vector<node> t(MAXN);
- int sz;
- struct state{ // нмймтелуе - аеоэ у нмцуфуз а оеюое и ноедия
- int v, pos;
- state(int v_, int pos_)
- {
- v = v_;
- pos = pos_;
- }
- };
- state ptr (0, 0); // аъпчйу а имоелщ
- state go(state st, int l, int r) // смпук номесчпщ анеоед ъпомия s[l, r)
- {
- while(l < r)
- {
- if(st.pos == t[st.v].len()) //неоехпу а ъй аеоэ еъйу кь ъпмук а имлфе оеюоч, а аеоэ ъммпа неоесмдя нм s[l]
- {
- st = state(t[st.v].get(s[l]), 0);
- if(st.v == -1)
- {
- return st;
- }
- }
- else
- {
- if(s[t[st.v].l + st.pos] != s[l]) // ъй ъукамй дмйтел юьпщ s[l]
- {
- return state(-1, -1);
- }
- if(r - l < t[st.v].len() - st.pos) // еъйу кмтлм ъочця номхпу анеоед дм имлфч пм удек (нм удее кмтеп юьпщ леаеолм)
- {
- return state(st.v, st.pos + r - l);
- }
- l += t[st.v].len() - st.pos;
- st.pos = t[st.v].len();
- }
- }
- return st;
- }
- int split(state st) // а пеияшек нмймтелуу оетек у амцаочшчек лмаяв аеоэуля
- {
- if(t[st.v].len() == st.pos)
- {
- return st.v;
- }
- if(st.pos == 0)
- {
- return t[st.v].par;
- }
- node v = t[st.v];
- int id = sz++; // ъмцдчйу лмаяв аеоэуля а ъеоедуле оеюоч, пенеощ келзек 4 ъъьйиу, мдлч яте еъпщ
- t[id] = node(v.l, v.l + st.pos, v.par);
- t[v.par].get( s[v.l] ) = id;
- t[id].get(s[v.l + st.pos]) = st.v;
- t[st.v].par = id;
- t[st.v].l += st.pos;
- return id;
- }
- int get_link(int v)
- {
- if(t[v].link != -1)
- {
- return t[v].link;
- }
- if(t[v].par == -1)
- {
- return 0;
- }
- int to = get_link(t[v].par);
- return t[v].link = split(go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));
- // удек мп ъярр ъъьйиу мп ноедич анеоед ъимйщим лчдм нм оеюоя у ле цчюьачек якелщэупщ дйуля лч 1 ълуця еъйу лчэ ноедми - имоелщ
- // дмючаич 1 ||||
- }
- void tree_extend(int pos)
- {
- while(true)
- {
- state nptr = go(ptr, pos, pos + 1);
- if(nptr.v != -1) // еъйу ъочця нмйябуймъщ номхпу - пм ми
- {
- ptr = nptr;
- return;
- }
- int mid = split(ptr);
- int leaf = sz++;
- t[leaf] = node(pos, n, mid);
- t[mid].get(s[pos]) = leaf;
- ptr.v = get_link(mid); // смпук дчйщэе номъкчпоуачпщ аъе ъярруиъь у номдйуачпщ ус лч ъукамй, нмич ле ноудек а имоелщ
- //йуюм нмич ъярруиъ анеоаье ле номдмйтупъз ъчк
- ptr.pos = t[ptr.v].len();
- if(!mid)
- {
- break;
- }
- }
- }
- void build_tree()
- {
- sz = 1;
- for(int i = 0; i < n; i++)
- {
- tree_extend(i);
- }
- }
- void read(vector<ll> &a)
- {
- for(int i = 0; i < a.size(); i++)
- {
- cin >> a[i];
- }
- }
- vector<ll> d(MAXN, 0), baks(MAXN, 0), dist(MAXN, 0);
- void dfs(int v, char c, int dst)
- {
- d[v] = 0;
- baks[v] = 0;
- ll ans = t[v].len();
- if(t[v].next.size() == 0)
- {
- baks[v] = 1;
- }
- dist[v] = dst;
- for(auto& item : t[v].next)
- {
- //cout << "HEHE";
- //cout << item.first << ' ' << item.second << ' ' << "NOMER" << ' ';
- dfs(item.second, item.first, dst + t[item.second].len());
- d[v] += d[item.second];
- baks[v] += baks[item.second];
- }
- d[v] += (dist[v] - ans) * ans * baks[v] + (ans + 1) * ans / 2 * baks[v];
- if(t[v].next.size() == 0)
- {
- //cout << "LST" << ' ' << d[v] << endl;
- d[v] -= (t[v].next.size() == 0) * dist[v];
- //cout << endl << "GEG" << endl;
- }
- //cout << endl << v << ' ' << dist[v] << ' ' << c << ' ' << d[v] << ' ' << t[v].len() << ' ' << baks[v] << endl;
- }
- char fnd(int v, ll col)
- {
- int ans = t[v].len();
- ll cur = (dist[v] - ans) * ans * baks[v] + (ans + 1) * ans / 2 * baks[v] - (t[v].next.size() == 0) * dist[v];
- //cout << "LMAO" << ' ' << v << ' ' << col << ' ' << cur << endl;
- /*if(t[v].next.size() == 0)
- {
- return s[t[v].l + col - 1];
- }*/
- //int cur = (dist[v] - ans) * ans * baks[v] + (ans + 1) * ans / 2 * baks[v] - (t[v].next.size() == 0) * dist[v];
- if(col <= cur)
- {
- //cout << "PEK";
- for(int i = 0; i < t[v].len(); i++)
- {
- // cout << "EPT";
- if(col <= (dist[v] - ans + i + 1) * baks[v])
- {
- 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) ];
- }
- col -= (dist[v] - ans + i + 1) * baks[v];
- }
- }
- //cout << "HEG";
- col -= cur;
- for(auto& item : t[v].next)
- {
- if(d[item.second] >= col)
- {
- //cout << "EBID";
- return fnd(item.second, col);
- }
- col -= d[item.second];
- }
- return 'h';
- }
- void write(int v)
- {
- cout << v << " ";
- for(auto& item : t[v].next)
- {
- cout << item.first << ' ' << item.second << ' ';
- }
- cout << endl;
- for(auto& item : t[v].next)
- {
- write(item.second);
- }
- }
- int main ()
- {
- //freopen("in.txt", "r", stdin);
- //freopen("out.txt", "w", stdout);
- ios::sync_with_stdio(0);cin.tie(0);
- int m;
- int ind = 1;
- while(cin >> m)
- {
- if(m == 0)
- {
- return 0;
- }
- s.clear();
- cin >> s;
- //cout << s;
- ptr = state(0, 0);
- s += '$';
- n = s.size();
- t.assign(MAXN, node());
- d.clear();
- baks.assign(0, MAXN);
- dist.clear();
- //t.resize(MAXN);
- build_tree();
- //write(0);
- //cout << sz << endl;
- vector<ll> a(m);
- read(a);
- dfs(0, '1', 0);
- cout << "Case #";
- cout << ind << ": ";
- ind++;
- for(int i = 0; i < m; i++)
- {
- //cout << "DHDHD";
- cout << fnd(0, a[i]);
- }
- cout << endl;
- //cout << d[min(3, sz - 1)] << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement