Advertisement
Guest User

2.B

a guest
May 23rd, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.50 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement