fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	const bool exhaustive_test = false, generate_test = true;
  6. 	using ll = long long;
  7. 	using ivector = vector<int>;
  8. 	using solver = function<void(int,int,ll,ll&)>;
  9. 	const ll inf = numeric_limits<ll>::max();
  10.     int N; cin >> N; ivector A(N), ones(N);
  11. 	const solver brute_force = [&](int k, int n, ll p, ll &ans) {
  12.         if (k == n)
  13.             ans = p;
  14.         else {
  15.             int i = ones[k], t = k+1, l = i-1, r = i+1;
  16.             for (ll u = p+1; (l >= 0 or r < N) and u < ans; --l, ++r, ++u) {
  17.                 if (l >= 0 and A[l] == 0)
  18.                     A[l] = -1, brute_force(t,n,u,ans), A[l] = 0;
  19.                 if (r < N and A[r] == 0 and u < ans)
  20.                     A[r] = -1, brute_force(t,n,u,ans), A[r] = 0; } } };
  21. 	const solver greedy = [&](int k, int n, ll p, ll &ans) {
  22. 		if (k == n)
  23. 			ans = p;
  24. 		else {
  25. 			int i = ones[k], t = k+1, l = i-1, r = i+1, u = p+1, v = p+1;
  26. 			while (l >= 0 and A[l] != 0 and u < ans)
  27. 				--l, ++u;
  28. 			if (l >= 0 and A[l] == 0 and u < ans)
  29. 				A[l] = -1, greedy(t,n,u,ans), A[l] = 0;
  30. 			while (r < N and A[r] != 0 and v < ans)
  31. 				++r, ++v;
  32. 			if (r < N and A[r] == 0 and v < ans)
  33. 				A[r] = -1, greedy(t,n,v,ans), A[r] = 0; } };
  34. 	if (exhaustive_test) {
  35.         for (int U = 1<<N, s = 1; s < U; ++s)
  36.             if (2*__builtin_popcount(s) <= N) {
  37.     			ll b = inf, g = inf; int n = 0;
  38. 				for (int p = 1, i = 0; i < N; ++i, p <<= 1)
  39.     				if (A[i] = 0, s&p)
  40.     					A[i] = 1, ones[n++] = i;
  41.     			if (brute_force(0,n,0,b), greedy(0,n,0,g), b != g) {
  42. 					for (int i = 0; i < N; ++i)
  43. 						cout << A[i] << ' ';
  44. 					cout << endl;
  45. 					cout << "brute_force = " << b << endl;
  46. 					cout << "greedy      = " << g;
  47. 					return 0; } }
  48. 		cout << "Passed"; }
  49. 	else {
  50.         if (generate_test) {
  51.             random_device device;
  52.             mt19937_64 rng(device());
  53.             uniform_int_distribution<int> uniform(1,N/2);
  54.             const auto b = A.begin(), e = A.end();
  55.             fill(b,b+uniform(rng),1), shuffle(b,e,rng), cout << N << endl << A[0];
  56.             for (int i = 1; i < N; ++i)
  57.                 cout << ' ' << A[i];
  58.             cout << endl; }
  59.         else {
  60.             for (int i = 0; i < N; ++i)
  61.                 cin >> A[i]; }
  62. 		int n = 0;
  63. 		for (int i = 0; i < N; ++i)
  64. 			if (A[i] == 1)
  65. 				ones[n++] = i;
  66. 		ll ans = inf;
  67. 		greedy(0,n,0,ans), cout << ans; }
  68.     return 0; }
  69.  
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
17
stdout
copy 
17
1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0
34
https://ideone.com/ZSvyq9
language:
C++14 (gcc 8.3)
created:
1 year 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!