fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int M = 32;
  5. int n;
  6. int x[16]; // x[i] in 1 .. M
  7. int y[16];
  8.  
  9. int F[M+1];
  10. int f(int x){return F[x] == x ? x : F[x] = f(F[x]);}
  11. bool important[M+1];
  12. int flux[M+1]; // from i to i+1
  13.  
  14. void merge(int a, int b)
  15. {
  16. 	int fa = f(a), fb = f(b);
  17. 	if(fa != fb)
  18. 		F[fa] = fb;
  19. }
  20.  
  21. struct edge
  22. {
  23. 	int a, b, len;
  24. 	bool operator <(const edge that)const
  25. 	{
  26. 		return len < that.len;
  27. 	}
  28. };
  29.  
  30. int solve()
  31. {
  32. 	for(int i = 1; i <= M; i++)
  33. 		F[i] = i;
  34. 	memset(flux, 0, sizeof(flux));
  35. 	memset(important, false, sizeof(important));
  36. 	for(int i = 0; i < n; i++)
  37. 	{
  38. 		merge(x[i], y[i]);
  39. 		important[x[i]] = important[y[i]] = true;
  40.  
  41. 		if(x[i] < y[i])
  42. 			for(int j = x[i]; j < y[i]; j++)
  43. 				flux[j] ++;
  44. 		if(x[i] > y[i])
  45. 			for(int j = y[i]; j < x[i]; j++)
  46. 				flux[j] --;
  47. 	}
  48. 	int ans = 0;
  49. 	for(int i = 1; i < M; i++)
  50. 	{
  51. 		if(flux[i] < 1)
  52. 			merge(i, i+1);
  53. 		if(flux[i] > 1)
  54. 		{
  55. 			ans += flux[i] - 1;
  56. 			merge(i, i+1);
  57. 		}
  58. 	}
  59. 	vector <edge> lis;
  60. 	int prevImportant = -1;
  61. 	for(int i = 1; i <= M; i++)
  62. 		if(important[i])
  63. 		{
  64. 			if(prevImportant != -1)
  65. 			{
  66. 				if(f(prevImportant) != f(i))
  67. 				{
  68. 					edge e;
  69. 					e.a = prevImportant;
  70. 					e.b = i;
  71. 					e.len = i - prevImportant;
  72. 					lis.push_back(e);
  73. 				}
  74. 			}
  75. 			prevImportant = i;
  76. 		}
  77. 	sort(lis.begin(), lis.end());
  78. 	for(int i = 0; i < lis.size(); i++)
  79. 	{
  80. 		if(f(lis[i].a) != f(lis[i].b))
  81. 		{
  82. 			ans += lis[i].len;
  83. 			merge(lis[i].a, lis[i].b);
  84. 		}
  85. 	}
  86. 	return ans;
  87. }
  88.  
  89. int dp[1<<16][16];
  90.  
  91. int dodp(int mask, int last)
  92. {
  93. 	if(mask == (1<<n)-1) return 0;
  94. 	int &ret = dp[mask][last];
  95. 	if(ret != -1) return ret;
  96. 	ret = 1000000000;
  97. 	for(int i = 0; i < n; i++)
  98. 		if((mask & (1<<i)) == 0)
  99. 			ret = min(ret, dodp(mask | (1<<i) , i) + max(0, y[last] - x[i]));
  100. 	return ret;
  101. }
  102.  
  103. int bruteforce()
  104. {
  105. 	memset(dp, 0xff, sizeof(dp));
  106. 	int ret = 1000000000;
  107. 	for(int i = 0; i < n; i++)
  108. 		ret = min(ret, dodp(1<<i, i));
  109. 	return ret;
  110. }
  111.  
  112. int MAIN()
  113. {
  114. 	srand((unsigned)time(NULL));
  115. 	int nCorrect = 0;
  116. 	for(int testCase = 1; testCase <= 500; testCase ++)
  117. 	{
  118. 		/*cin >> n;
  119. 		for(int i = 0; i < n; i++)
  120. 			cin >> x[i];
  121. 		for(int i = 0; i < n; i++)
  122. 			cin >> y[i];*/
  123. 		n = rand() % 16 + 1;
  124. 		for(int i = 0; i < n; i++)
  125. 		{
  126. 			x[i] = rand() % 32 + 1;
  127. 			y[i] = rand() % 32 + 1;
  128. 		}
  129. 		int ansBF = bruteforce();
  130. 		int ans = solve();
  131. 		if(ansBF != ans) cout << "ERROR" << endl;
  132. 		else nCorrect ++;
  133. 	}
  134. 	cout << nCorrect << " correct " << endl;
  135. 	return 0;
  136. }
  137.  
  138. int main()
  139. {
  140. 	int start = clock();
  141. 	#ifdef LOCAL_TEST
  142. 		freopen("in.txt", "r", stdin);
  143. 		freopen("out.txt", "w", stdout);
  144. 	#endif
  145. 	ios :: sync_with_stdio(false);
  146. 	cout << fixed << setprecision(16);
  147. 	int ret = MAIN();
  148. 	#ifdef LOCAL_TEST
  149. 		cout << "[Finished in " << clock() - start << " ms]" << endl;
  150. 	#endif
  151. 	return ret;
  152. }
  153.  
Success #stdin #stdout 2.34s 7564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
500 correct
https://ideone.com/S0V4Up
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!