Advertisement
Guest User

Untitled

a guest
Oct 5th, 2015
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.53 KB | None | 0 0
  1. #include <cstring>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <stack>
  7. #include <bitset>
  8. #include <algorithm>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17. typedef pair<int, int> ii;
  18. #define pb push_back
  19. const int maxn = (int) 1e6 + 5;
  20. const int mod = (int) 1e9 + 7;
  21.  
  22.  
  23. int n, q;
  24. int l[maxn];
  25. vector<int> G[maxn];
  26. int lcm;
  27. int M[maxn][32];
  28.  
  29. int main(){
  30. ///freopen("test.txt", "r", stdin);
  31. cin >> n >> q;
  32. lcm = 1;
  33. for (int i = 1; i <= n; i ++) {
  34. cin >> l[i];
  35. int x = __gcd(l[i], lcm);
  36. lcm = lcm / x;
  37. lcm *= l[i];
  38. for (int j = 1; j <= l[i]; j ++) {
  39. int x; cin >> x;
  40. G[i].pb(x);
  41. }
  42. }
  43.  
  44. for (int i = 0; i < lcm; i ++) {
  45. for (int j = 1; j <= n; j++) {
  46. int u = i * n + j;
  47. int x = G[j][i % l[j]];
  48. int v = ((i + 1) % lcm) * n + x;
  49. M[u][0] = v;
  50. }
  51. }
  52.  
  53. for (int k = 1; k < 32; k ++) {
  54. for (int i = 1; i <= n * lcm; i ++) {
  55. M[i][k] = M[M[i][k - 1]][k - 1];
  56. }
  57. }
  58.  
  59. while (q --){
  60. ll t; cin >> t; t--;
  61. ll res = 1;
  62. for (int i = 31; i >= 0; i--){
  63. if((1LL << i) <= t) {
  64. res = M[res][i];
  65. t -= (1LL << i);
  66. }
  67. }
  68. res = (res % n);
  69. if(res == 0) res = n;
  70. cout << res << endl;
  71. }
  72.  
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement