fork download
copy 
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. int sum_of_array(int A[], int N);
  6. void mover(int A[], int i, int j);
  7. int run_through(int A[], int N, int D);
  8. bool all_equal(int A[], int N);
  9. bool possible(int A[], int N, int D);
  10. void smaller(int A[], int i, int mean, int D, int &x, int N);
  11. void bigger(int A[], int i, int mean, int D, int &x, int N);
  12.  
  13. int main()
  14. {
  15. 	const int SIZE = 100005;
  16. 	int T, N, D, A[SIZE], X[12];
  17. 	cin>>T;
  18. 	for(int i=0; i<T; ++i)
  19. 	{
  20. 		cin>>N;
  21. 		cin>>D;
  22.  
  23. 		for(int j=0; j<N; ++j) cin>>A[j];
  24.  
  25. 		if(!possible(A, N, D)) X[i] = -1;
  26. 		else if(all_equal(A, N)) X[i] = 0;
  27. 		else X[i] = run_through(A, N, D);
  28. 	}
  29.  
  30. 	for(int i=0; i<T; ++i) cout<<X[i]<<"\n";
  31.  
  32. 	return 0;
  33. }
  34.  
  35. int sum_of_array(int A[], int N)
  36. {
  37. 	int sum = A[0];
  38. 	for(int i=1; i<N; ++i) sum+=A[i];
  39. 	cout << "sum = " << sum << endl;
  40. 	return sum;
  41. }
  42.  
  43. void mover(int A[], int i, int j)
  44. {
  45. 	A[i]--;
  46. 	A[j]++;
  47. }
  48.  
  49. int run_through(int A[], int N, int D)
  50. {
  51. 	int x = 0;
  52. 	int mean = sum_of_array(A, N)/N;
  53. 	for(int i=0; i<N; ++i)
  54. 	{
  55. 		cout << "A[" << i << "] = " << A[i] << endl;
  56. 		if(A[i]>mean && i+D<N) bigger(A, i, mean, D, x, N);
  57. 		else if(A[i]<mean && i+D<N) smaller(A, i, mean, D, x, N);
  58. 	}
  59. 	if(x==0 || !all_equal(A, N)) return -1;
  60. 	else return x;
  61. }
  62.  
  63. bool all_equal(int A[], int N)
  64. {
  65. 	for(int i=1; i<N; ++i) if(A[0]!=A[i]) return false;
  66. 	return true;
  67. }
  68.  
  69. bool possible(int A[], int N, int D)
  70. {
  71. 	if(sum_of_array(A, N)%N!=0) return false;
  72. 	if(!all_equal(A, N) && (D==0 || D>N-1)) return false;
  73. 	return true;
  74. }
  75.  
  76. void smaller(int A[], int i, int mean, int D, int &x, int N)
  77. {
  78. 	int j=i+D;
  79. 	while(A[i]<mean && j<N)
  80. 	{
  81. 		if(A[j]>0)
  82. 		{
  83. 			mover(A, j, i);
  84. 			x+=(j-i)/D;
  85. 		}
  86. 		else j+=D;
  87. 	}
  88. }
  89.  
  90. void bigger(int A[], int i, int mean, int D, int &x, int N)
  91. {
  92. 	while(A[i]>mean)
  93. 	{
  94. 		mover(A, i, i+D);
  95. 		x++;
  96. 	}
  97. }
Success #stdin #stdout 3.63s 16336KB
comments (?)
stdin
copy 
1
4 2
1000000000 900000000 800000000 900000000
stdout
copy 
sum = -694967296
sum = -694967296
A[0] = 1000000000
A[1] = 900000000
A[2] = 1973741824
A[3] = 1973741824
-1
https://ideone.com/Pf9eJ7
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!