fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. const int N = 100010 * 64;
  4. typedef long long ll;
  5. int tr[N];
  6. int lp[N];
  7. int rp[N];
  8. int lastn = 2;
  9. ll getk(int &cur, ll l, ll r, ll k)
  10. {
  11. 	if (cur == 0) cur = lastn++;
  12. 	tr[cur]++;
  13. 	if (l == r)
  14. 		return l;
  15. 	ll m = (l + r) / 2;
  16. 	ll lsize = m - l + 1 - tr[lp[cur]];
  17. 	if (lsize >= k)
  18. 		return getk(lp[cur], l, m, k);
  19. 	else
  20. 		return getk(rp[cur], m + 1, r, k - lsize);
  21. }
  22. int root = 1;
  23. int main()
  24. {
  25. 	ios::sync_with_stdio(false);
  26. 	ll n, k;
  27. 	cin >> n >> k;
  28. 	ll p = 0;
  29. 	for (int i = 0; i < k; ++i){
  30. 		ll x;
  31. 		cin >> x;
  32. 		p = (p + x - 1) % (n - i) + 1;
  33. 		ll res = getk(root, 1, n, p);
  34. 		cout << res << ' ';
  35. 		--p;
  36. 	}
  37. 	cout << '\n';
  38. 	return 0;
  39. }
Success #stdin #stdout 0s 78464KB
comments (?)
stdin
copy 
10 5
2 7 1 8 2
stdout
copy 
2 9 10 1 4
https://ideone.com/MF8qBK
10 5
2 7 1 8 2
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!