Submission #471853

#	Time	Username	Problem	Language	Result	Execution time	Memory
471853		prvocislo	Lamps (JOI19_lamps)	C++17	47 / 100	1076 ms	113808 KiB

lamp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
typedef long long ll;
using namespace std;

const int inf = 1e9 + 5;
void upd(int& a, const int& b) { a = min(a, b); }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	string sa, sb;
	cin >> n >> sa >> sb;
	vector<int> a, b;
	for (int i = 0; i < n; i++) a.push_back(sa[i] == '1');
	for (int i = 0; i < n; i++) b.push_back(sb[i] == '1');
	map<vector<int>, int> m;
	int cnt = 0;
	for (int i = 0; i < 8; i++)
	{
		vector<int> v;
		for (int j = 0; j < 3; j++) if (i & (1 << j)) v.push_back(j);
		do
		{
			if (!m.count(v)) m[v] = cnt++;
		} while (next_permutation(v.begin(), v.end()));
	}
	vector<vector<int> > dp(n + 1, vector<int>(cnt, inf));
	dp[0][m[{}]] = 0;
	for (int i = 0; i < n; i++)
	{
		// ideme ukoncit par zmien
		for (const pair<vector<int>, int>& p : m)
		{
			for (int j = 0; j < (1 << p.first.size()); j++)
			{
				vector<int> x;
				for (int k = 0; k < p.first.size(); k++) if (j & (1 << k))
					x.push_back(p.first[k]);
				upd(dp[i][m[x]], dp[i][p.second]);
			}
		}
		// ideme vytvorit par zmien
		for (const pair<vector<int>, int>& p : m)
		{
			for (int j = 0; j < (1 << p.first.size()); j++)
			{
				vector<int> x;
				for (int k = 0; k < p.first.size(); k++) if (j & (1 << k))
					x.push_back(p.first[k]);
				upd(dp[i][p.second], dp[i][m[x]] + p.first.size() - x.size());
			}
		}
		// ideme na dalsi prvok
		for (const pair<vector<int>, int>& p : m)
		{
			int val = a[i];
			for (int j : p.first)
			{
				if (j == 0) val = 0;
				if (j == 1) val = 1;
				if (j == 2) val = !val;
			}
			if (val == b[i]) upd(dp[i + 1][p.second], dp[i][p.second]);
		}
	}
	int ans = inf;
	for (int i = 0; i < dp[n].size(); i++) upd(ans, dp[n][i]);
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int k = 0; k < p.first.size(); k++) if (j & (1 << k))
      |                     ~~^~~~~~~~~~~~~~~~
lamp.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int k = 0; k < p.first.size(); k++) if (j & (1 << k))
      |                     ~~^~~~~~~~~~~~~~~~
lamp.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < dp[n].size(); i++) upd(ans, dp[n][i]);
      |                  ~~^~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49