Advertisement
Guest User

Untitled

a guest
Jun 27th, 2017
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. int k, n;
  9. ll m;
  10.  
  11. int p[1 << 20];
  12. int to[1 << 20];
  13. int nx[1 << 20];
  14. int cr[1<<20];
  15.  
  16. void solve() {
  17. cin >> n >> k >> m;
  18. for (int i = 0; i < n; i++) {
  19. scanf("%lld", p + i);
  20. }
  21.  
  22. to[0] = k;
  23. to[n-1] = n-1-k;
  24. int l = 0;
  25. int r = k;
  26. for (int i = 1; i < n - 1; i++) {
  27. while (r < n - 1) {
  28. if (p[r+1] - p[i] < p[i] - p[l]) {
  29. r++; l++;
  30. } else break;
  31. }
  32.  
  33. if (p[i] - p[l] >= p[r] - p[i]) to[i] = l; else to[i] = r;
  34. }
  35.  
  36. for (int i = 0; i < n; i++) cr[i] = i;
  37.  
  38. while (m) {
  39. if (m & 1) {
  40. for (int i = 0; i < n; i++)
  41. cr[i] = to[cr[i]];
  42. }
  43. for (int i = 0; i < n; i++)
  44. nx[i] = to[to[i]];
  45.  
  46. for (int i = 0; i < n; i++) to[i] = nx[i];
  47. m /= 2;
  48. }
  49. for (int i = 0; i < n; i++) {
  50. if (i) printf(" ");
  51. printf("%d", cr[i]+1);
  52. }
  53. cout << endl;
  54. }
  55.  
  56. int main() {
  57. //freopen("input.txt","r",stdin);
  58. //freopen("output.txt","w",stdout);
  59.  
  60. solve();
  61.  
  62. return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement