fork download
  1. /*
  2. ye mera template hai
  3. apna khud likho bc :P
  4. */
  5.  
  6. /*
  7. Author : Sarvagya Agarwal
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12.  
  13. //defines
  14. #define openin freopen("input.txt","r",stdin)
  15. #define openout freopen("output.txt","w",stdout)
  16. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  17. #define ll long long
  18. #define mod 1000000007
  19. #define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
  20. #define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
  21. #define all(c) (c).begin(),(c).end()
  22. #define ff first
  23. #define ss second
  24. #define pb push_back
  25. #define mp make_pair
  26.  
  27. /* Print pair */
  28. template <typename T,typename S>
  29. ostream & operator << (ostream &os , const pair<T,S> &v) {
  30. os << "(" ;
  31. os << v.first << "," << v.second << ")" ;
  32. return os ;
  33. }
  34. /* Print vector */
  35. template <typename T>
  36. ostream & operator << (ostream &os , const vector<T> &v) {
  37. os << "[" ;
  38. int sz = v.size() ;
  39. for(int i = 0 ; i < sz ; ++i) {
  40. os << v[i] ;
  41. if(i!=sz-1)os << "," ;
  42. }
  43. os << "]\n" ;
  44. return os ;
  45. }
  46. /* Print set */
  47. template <typename T>
  48. ostream & operator << (ostream &os , const set<T> &v) {
  49. T last = *v.rbegin() ;
  50. os << "[" ;
  51. for(auto it : v) {
  52. os << it ;
  53. if(it != last) os << "," ;
  54. }
  55. os << "]\n" ;
  56. return os ;
  57. }
  58. /* Print Map */
  59. template <typename T,typename S>
  60. ostream & operator << (ostream &os , const map<T,S> &v) {
  61. for(auto it : v) {
  62. os << it.first << " : " << it.second << "\n" ;
  63. }
  64. return os ;
  65. }
  66. int power(int a , int b)
  67. {
  68. int res = 1 ;
  69. while(b)
  70. {
  71. if(b%2) {
  72. res = (res * a) % mod ;
  73. }
  74. b/=2 ;
  75. a = (a*a) % mod ;
  76. }
  77. return res ;
  78. }
  79.  
  80. //debug
  81. #define TRACE
  82.  
  83. #ifdef TRACE
  84. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  85. template <typename Arg1>
  86. void __f(const char* name, Arg1&& arg1){
  87. cerr << name << " : " << arg1 << std::endl;
  88. }
  89. template <typename Arg1, typename... Args>
  90. void __f(const char* names, Arg1&& arg1, Args&&... args){
  91. const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  92. }
  93. #else
  94. #define trace(...)
  95. #endif
  96. bool is_power_of_two(int n)
  97. {
  98. if(n == 0) return false ;
  99. return (n & (n-1)) == 0 ;
  100. }
  101. int count_bits(int n)
  102. {
  103. return __builtin_popcount(n) ;
  104. }
  105. int count_bits_ll(int n)
  106. {
  107. return __builtin_popcountll(n) ;
  108. }
  109. int largest_power(int n)
  110. {
  111. int i ;
  112. for(i = 1 ; i <= n ; i *= 2) ;
  113. return i/2 ;
  114. }
  115. const int N = 1e6 + 5 ;
  116. int n , arr[N * 4] , rem ;
  117. void update(int i,int l,int r,int idx,int val)
  118. {
  119. if(l == r) {
  120. arr[i] = val ;
  121. return ;
  122. }
  123. int m = (l + r) / 2 ;
  124. if(idx <= m) update(i*2,l,m,idx,val) ;
  125. else update(i*2+1,m+1,r,idx,val) ;
  126. arr[i] = arr[i*2] + arr[i*2+1] ;
  127. }
  128. void build(int i,int l,int r)
  129. {
  130. if(l == r) {
  131. arr[i] = 1 ;
  132. return ;
  133. }
  134. int m = l + r >> 1 ;
  135. build(i * 2 , l , m ) ;
  136. build(i * 2 + 1 , m + 1 , r) ;
  137. arr[i] = arr[i*2] + arr[i*2+1] ;
  138. }
  139. int query_cnt(int i,int l,int r,int s,int e)
  140. {
  141. if(l > r || r < s || l > e) return 0 ;
  142. if(l >= s and r <= e) return arr[i] ;
  143. int m = l + r >> 1 ;
  144. return query_cnt(i*2,l,m,s,e) + query_cnt(i*2+1,m+1,r,s,e) ;
  145. }
  146. int query(int i,int l,int r,int k)
  147. {
  148. //trace(i,l,r,k,arr[i]);
  149. if(l==r) return l ;
  150. int m = (l + r) >> 1 ;
  151. int L = arr[i * 2] ;
  152. int R = arr[i*2+1] ;
  153. if(k <= L) return query(i*2,l,m,k) ;
  154. else return query(i*2+1,m+1,r,k-L) ;
  155. }
  156. int get_c(int index , int k)
  157. {
  158. if(k > rem)k %= rem ;
  159. if(k == 0) k = rem ;
  160. // return kth remaining from index 'index'
  161. int cnt = query_cnt(1,1,n,index,n) ;
  162. int cnt2 = query_cnt(1,1,n,1,index-1) ;
  163. if(k <= cnt) {
  164. return query(1,1,n,cnt2 + k) ;
  165. }
  166. else {
  167. return query(1,1,n,k-cnt) ;
  168. }
  169. }
  170. int get_ac(int index , int k)
  171. {
  172.  
  173. if(k > rem)k %= rem ;
  174. if(k == 0) k = rem ;
  175. // return kth remaining from index 'index'
  176. int cnt = query_cnt(1,1,n,index+1,n) ;
  177. int cnt2 = query_cnt(1,1,n,1,index) ;
  178. if(k <= cnt2) {
  179. return query(1,1,n,cnt2+1-k) ;
  180. }
  181. else {
  182. return query(1,1,n,cnt-k+1+cnt2+cnt2) ;
  183. }
  184. }
  185. int main()
  186. {
  187. int t ;
  188. scanf("%d",&t) ;
  189. //cin >> t ;
  190. while(t--) {
  191. scanf("%d",&n) ;ll k ; scanf("%lld",&k) ;
  192. build(1,1,n) ;
  193. rem = n ;
  194. if(k > 0) {
  195. int index = 1 ;
  196. ll kk = k ;
  197. bool clock = true ;
  198. rep(i,1,n-1) {
  199. int temp ;
  200. if(clock) {
  201. temp = get_c(index , kk) ;
  202. }
  203. else {
  204. temp = get_ac(index , kk) ;
  205. }
  206. update(1,1,n,temp,0) ;
  207. index = temp ;
  208. clock ^= true ;
  209. kk += k ; rem-- ;
  210. }
  211. printf("%d\n",query(1,1,n,1));// << "\n" ;
  212. }
  213. else {
  214. int index = 1 ;
  215. ll kk = k ;
  216. bool clock = false ;
  217. rep(i,1,n-1) {
  218. int temp ;
  219. if(clock) {
  220. temp = get_c(index , -kk) ;
  221. }
  222. else {
  223. temp = get_ac(index , -kk) ;
  224. }
  225. update(1,1,n,temp,0) ;
  226. index = temp ;
  227. clock ^= true ;
  228. kk += k ;rem--;
  229. }
  230. printf("%d\n",query(1,1,n,1));
  231. }
  232. }
  233. return 0;
  234. }
  235.  
Time limit exceeded #stdin #stdout 5s 8376320KB
stdin
Standard input is empty
stdout
Standard output is empty