fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5.  
  6. using namespace std; 
  7.  
  8. #define sz(x) x.size
  9. #define pb push_back
  10. #define all(x) x.begin(),x.end()
  11.  
  12. // my vector
  13. struct vec{
  14. 	int a[20100], size;
  15. 	vec() { memset(a,0,sizeof a); }
  16. 	void resize(int n) { size = n; }
  17. 	void assign(int n, int val) {
  18. 		size = n;
  19. 		for (int i = 0; i < n; i++)
  20. 			a[i] = val;
  21. 	}
  22. 	void push_back(int x) {
  23. 		a[size++] = x;
  24. 	}
  25. 	void clear() { size = 0; }
  26. 	int* begin() { return a; }
  27. 	int* end() { return a+size; }
  28. 	int& operator[] (int i) { return a[i]; }
  29. };
  30.  
  31. vec a, b, chain, u, allshifts, save, ptr, st, oldptr;
  32.  
  33. int N, M, W, Q, shifts, v, cheaton;
  34.  
  35. // adds all chain of shifts to chain
  36. void find_chain(int v) {
  37. 	while (true) {
  38. 		u[v] = 1;
  39. 		st.pb(v);
  40. 		chain.pb(v);
  41. 		save[v] = a[v];
  42. 		int val = a[v];
  43. 	   	int &to = ptr[val];
  44. 		while (to < N && (u[to] || a[to] == val) && b[to] == val)
  45. 			to++;
  46. 		if (to == N || b[to] != val)
  47. 			return;
  48. 		v = to;
  49. 	}
  50. }
  51.  
  52. int main() {
  53. 	// input
  54. 	scanf("%d%d%d", &N, &M, &W);
  55. 	a.resize(N);
  56. 	ptr.resize(M+1);
  57. 	v = N-1;
  58.  
  59. 	for (int i = 0; i < N; i++)
  60. 		scanf("%d", &a[i]);
  61.  
  62. 	// b = sorted(a)
  63. 	b = save = a;
  64. 	stable_sort(all(b));
  65.  
  66. 	// ptr[i] points at first 
  67. 	// position of i in sorted array b
  68. 	// O(MlgN)
  69. 	for (int i = 1; i <= M; i++)
  70. 		ptr[i] = lower_bound(all(b), i) - b.begin();
  71.  
  72. 	Q = (N+W-2) / (W-1);
  73. 	// for every round out of Q
  74. 	printf("%d\n", Q);
  75.  
  76. 	// next cycle works O(N/W) time
  77. 	while (Q--) {
  78. 		// if there is no need to
  79. 		// do anything, just output zero
  80. 		if (cheaton) {
  81. 			puts("0");
  82. 			continue;
  83. 		}
  84.  
  85. 		shifts = 0;
  86. 		allshifts.clear();
  87.  
  88. 		for (int i = 0; i <= M; i++)
  89. 			oldptr[i] = ptr[i];
  90.  
  91. 		// until number of shifts < W
  92. 		while (shifts < W) {				// O(W)
  93. 			chain.clear();
  94. 			// find any number standing wrong
  95. 			while (v >= 0 && (u[v] || a[v] == b[v]))
  96. 				v--;
  97. 			if (v == -1) 
  98. 				break;
  99. 			find_chain(v);
  100. 			// add chain until we fillup shifts
  101. 			chain.resize(min(sz(chain), W-shifts));
  102. 			for (int i = 0; i < sz(chain); i++) {
  103. 				allshifts.pb(chain[i]);
  104. 				allshifts.pb(chain[(i+1)%sz(chain)]);
  105. 			}
  106.  
  107. 			shifts += sz(chain);
  108. 		}
  109.  
  110. 		// if there are no changes, 
  111. 		// no need to output anything but zeroes
  112. 		if (!shifts)
  113. 			cheaton = 1;
  114.  
  115. 		// output all changes
  116. 		printf("%d ", shifts);
  117. 		for (int i = 0; i < sz(allshifts); i++)
  118. 			printf("%d ", allshifts[i]+1);
  119. 		printf("\n");
  120.  
  121. 		// apply all chains now
  122. 		for (int i = 0; i < sz(allshifts); i += 2)
  123. 			a[allshifts[i+1]] = save[allshifts[i]];
  124.  
  125. 		// move all ptrs as far as possible
  126. 		for (int i = 1; i <= M; i++) {
  127. 			ptr[i] = oldptr[i];
  128. 			int &o = ptr[i];
  129. 			while (o < N && b[o] == i && a[o] == i)
  130. 				o++;
  131. 		}
  132.  
  133. 		// clear used array
  134. 		for (int i = 0; i < sz(st); i++)
  135. 			u[st[i]] = 0;
  136. 		st.clear();
  137.  
  138. 	}
  139.  
  140. 	return 0;
  141. }
  142.  
Success #stdin #stdout 0.02s 3392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
0 
0
https://ideone.com/mWjMh
language:
C++ (gcc 8.3)
created:
12 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!