fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZtQWL7
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!