Submission #554629

#	Time	Username	Problem	Language	Result	Execution time	Memory
554629		pavement	Lamps (JOI19_lamps)	C++17	0 / 100	1073 ms	4172 KiB

lamp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N;
vector<int> dp[2];
bool A[1000005], B[1000005];
char C;

vector<ii> vec;

bool apply(bool x, int b) {
	int bm = vec[b].second;
	for (int k = 0; k < vec[b].first; k++) {
		if (bm % 3 == 0) x = 0;
		else if (bm % 3 == 1) x = 1;
		else x ^= 1;
		bm /= 3;
	}
	return x;
}

int cst(int a, int b) {
	int lcp = 0, bma = vec[a].second, bmb = vec[b].second;
	for (int i = 0; i < min(vec[a].first, vec[b].first); i++) {
		if (bma % 3 == bmb % 3) lcp = i + 1;
		else break;
		bma /= 3;
		bmb /= 3;
	}
	return vec[b].first - lcp;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0, p = 1; i <= 6; i++) {
		for (int j = 0; j < p; j++) vec.eb(i, j);
		p *= 3;
	}
	for (int i = 1; i <= N; i++) {
		cin >> C;
		A[i] = C == '1';
	}
	for (int i = 1; i <= N; i++) {
		cin >> C;
		B[i] = C == '1';
	}
	dp[0].resize(vec.size());
	dp[1].resize(vec.size());
	for (int i = N; i >= 1; i--)
		for (int b = 0; b < vec.size(); b++) {
			dp[i & 1][b] = INT_MAX;
			for (int nb = 0; nb < vec.size(); nb++)
				if (apply(A[i], nb) == B[i]) dp[i & 1][b] = min(dp[i & 1][b], dp[i & 1 ^ 1][nb] + cst(b, nb));
		}
	cout << dp[1][0] << '\n';
}

Compilation message (stderr)

lamp.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main() {
      | ^~~~
lamp.cpp: In function 'int main()':
lamp.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int b = 0; b < vec.size(); b++) {
      |                   ~~^~~~~~~~~~~~
lamp.cpp:79:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for (int nb = 0; nb < vec.size(); nb++)
      |                     ~~~^~~~~~~~~~~~
lamp.cpp:80:72: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   80 |     if (apply(A[i], nb) == B[i]) dp[i & 1][b] = min(dp[i & 1][b], dp[i & 1 ^ 1][nb] + cst(b, nb));
      |                                                                      ~~^~~

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