fork download
copy 
  1. #include <vector>
  2. #include <map>
  3. #include <set>
  4. #include <deque>
  5. #include <queue>
  6. #include <stack>
  7. #include <algorithm>
  8. #include <numeric>
  9. #include <utility>
  10. #include <sstream>
  11. #include <iostream>
  12. #include <iomanip>
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <cstdlib>
  16. #include <ctime>
  17. #include <cstring>
  18. #include <assert.h>
  19.  
  20. using namespace std;
  21.  
  22. #define sz(a) (int)(a.size())
  23. #define len(a) (int)(a.length())
  24. #define pb push_back
  25. #define mp make_pair
  26. #define fi first
  27. #define se second
  28.  
  29. inline long long ab(long long x) {return x<0?-x:x;}
  30.  
  31. long long f(long long k,vector<int>&x)
  32. {
  33. 	long long steps=0;
  34. 	for(int i=0;i<sz(x);++i)
  35. 		steps+=ab(x[i]-k);
  36. 	return steps;
  37. }
  38.  
  39. class FoxConnection3 {
  40. public:
  41. 	long long minimalSteps(vector <int> x, vector <int> y)
  42. 	{
  43. 		//Y
  44. 		long long lo=-20000000000LL,hi=20000000000LL,res=-1;
  45. 		while(lo<=hi)
  46. 		{
  47. 			long long mid=(lo+hi)>>1;
  48. 			if(f(mid,y)<=f(mid+1,y)) res=mid,hi=mid-1;
  49. 			else lo=mid+1;
  50. 		}
  51. 		//X
  52. 		lo=-20000000000LL,hi=20000000000LL;
  53. 		long long res2=-1;
  54. 		while(lo<=hi)
  55. 		{
  56. 			long long mid=(lo+hi)>>1;
  57. 			if(f(mid,x)<=f(mid+1,x)) res2=mid,hi=mid-1;
  58. 			else lo=mid+1;
  59. 		}
  60. 		return f(res,y)+f(res2,x);
  61. 	}
  62. };
  63.  
  64.  
  65. // BEGIN KAWIGIEDIT TESTING
  66. // Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
  67. #include <iostream>
  68. #include <string>
  69. #include <vector>
  70. using namespace std;
  71. bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, bool hasAnswer, long long p2) {
  72. 	cout << "Test " << testNum << ": [" << "{";
  73. 	for (int i = 0; int(p0.size()) > i; ++i) {
  74. 		if (i > 0) {
  75. 			cout << ",";
  76. 		}
  77. 		cout << p0[i];
  78. 	}
  79. 	cout << "}" << "," << "{";
  80. 	for (int i = 0; int(p1.size()) > i; ++i) {
  81. 		if (i > 0) {
  82. 			cout << ",";
  83. 		}
  84. 		cout << p1[i];
  85. 	}
  86. 	cout << "}";
  87. 	cout << "]" << endl;
  88. 	FoxConnection3 *obj;
  89. 	long long answer;
  90. 	obj = new FoxConnection3();
  91. 	clock_t startTime = clock();
  92. 	answer = obj->minimalSteps(p0, p1);
  93. 	clock_t endTime = clock();
  94. 	delete obj;
  95. 	bool res;
  96. 	res = true;
  97. 	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
  98. 	if (hasAnswer) {
  99. 		cout << "Desired answer:" << endl;
  100. 		cout << "\t" << p2 << endl;
  101. 	}
  102. 	cout << "Your answer:" << endl;
  103. 	cout << "\t" << answer << endl;
  104. 	if (hasAnswer) {
  105. 		res = answer == p2;
  106. 	}
  107. 	if (!res) {
  108. 		cout << "DOESN'T MATCH!!!!" << endl;
  109. 	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
  110. 		cout << "FAIL the timeout" << endl;
  111. 		res = false;
  112. 	} else if (hasAnswer) {
  113. 		cout << "Match :-)" << endl;
  114. 	} else {
  115. 		cout << "OK, but is it right?" << endl;
  116. 	}
  117. 	cout << "" << endl;
  118. 	return res;
  119. }
  120. int main() {
  121. 	bool all_right;
  122. 	all_right = true;
  123.  
  124. 	vector <int> p0;
  125. 	vector <int> p1;
  126. 	long long p2;
  127.  
  128. 	{
  129. 	// ----- test 0 -----
  130. 	int t0[] = {0,0,1,-2};
  131. 			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
  132. 	int t1[] = {1,-1,0,0};
  133. 			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
  134. 	p2 = 2ll;
  135. 	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
  136. 	// ------------------
  137. 	}
  138.  
  139. 	{
  140. 	// ----- test 1 -----
  141. 	int t0[] = {0,0,0,0,0,0};
  142. 			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
  143. 	int t1[] = {1,2,3,4,5,6};
  144. 			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
  145. 	p2 = 0ll;
  146. 	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
  147. 	// ------------------
  148. 	}
  149.  
  150. 	{
  151. 	// ----- test 2 -----
  152. 	int t0[] = {-123456789,-58585858,-47474747,123,456,789012345};
  153. 			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
  154. 	int t1[] = {0,0,0,0,0,0};
  155. 			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
  156. 	p2 = 1018530309ll;
  157. 	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
  158. 	// ------------------
  159. 	}
  160.  
  161. 	{
  162. 	// ----- test 3 -----
  163. 	int t0[] = {1,7,3,5,2};
  164. 			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
  165. 	int t1[] = {2,7,5,3,7};
  166. 			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
  167. 	p2 = 12ll;
  168. 	all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
  169. 	// ------------------
  170. 	}
  171.  
  172. 	{
  173. 	// ----- test 4 -----
  174. 	int t0[] = {-3,0,1,-2,3,2};
  175. 			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
  176. 	int t1[] = {2,-3,0,1,-1,-1};
  177. 			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
  178. 	p2 = 10ll;
  179. 	all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
  180. 	// ------------------
  181. 	}
  182.  
  183. 	{
  184. 	// ----- test 5 -----
  185. 	int t0[] = {-96277832,507856257,-86306299,-806700273,-775932643,-273209838};
  186. 			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
  187. 	int t1[] = {-955536464,-599634138,399850429,-165706338,-537800480,738983556};
  188. 			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
  189. 	p2 = 5247213600ll;
  190. 	all_right = KawigiEdit_RunTest(5, p0, p1, true, p2) && all_right;
  191. 	// ------------------
  192. 	}
  193.  
  194. 	{
  195. 	// ----- test 6 -----
  196. 	int t0[] = {0};
  197. 			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
  198. 	int t1[] = {0};
  199. 			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
  200. 	p2 = 0ll;
  201. 	all_right = KawigiEdit_RunTest(6, p0, p1, true, p2) && all_right;
  202. 	// ------------------
  203. 	}
  204.  
  205. 	if (all_right) {
  206. 		cout << "You're a stud (at least on the example cases)!" << endl;
  207. 	} else {
  208. 		cout << "Some of the test cases had errors." << endl;
  209. 	}
  210. 	return 0;
  211. }
  212. // END KAWIGIEDIT TESTING
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222. //Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!
  223.  
Success #stdin #stdout 0s 3236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test 0: [{0,0,1,-2},{1,-1,0,0}]
Time: 8e-06 seconds
Desired answer:
	2
Your answer:
	5
DOESN'T MATCH!!!!

Test 1: [{0,0,0,0,0,0},{1,2,3,4,5,6}]
Time: 9e-06 seconds
Desired answer:
	0
Your answer:
	9
DOESN'T MATCH!!!!

Test 2: [{-123456789,-58585858,-47474747,123,456,789012345},{0,0,0,0,0,0}]
Time: 8e-06 seconds
Desired answer:
	1018530309
Your answer:
	1018530318
DOESN'T MATCH!!!!

Test 3: [{1,7,3,5,2},{2,7,5,3,7}]
Time: 7e-06 seconds
Desired answer:
	12
Your answer:
	18
DOESN'T MATCH!!!!

Test 4: [{-3,0,1,-2,3,2},{2,-3,0,1,-1,-1}]
Time: 9e-06 seconds
Desired answer:
	10
Your answer:
	19
DOESN'T MATCH!!!!

Test 5: [{-96277832,507856257,-86306299,-806700273,-775932643,-273209838},{-955536464,-599634138,399850429,-165706338,-537800480,738983556}]
Time: 8e-06 seconds
Desired answer:
	5247213600
Your answer:
	5247213609
DOESN'T MATCH!!!!

Test 6: [{0},{0}]
Time: 4e-06 seconds
Desired answer:
	0
Your answer:
	0
Match :-)

Some of the test cases had errors.
https://ideone.com/cWUIBR
language:
C++14 (gcc 8.3)
created:
9 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!