Submission #554632

#	Time	Username	Problem	Language	Result	Execution time	Memory
554632		pavement	Lamps (JOI19_lamps)	C++17	6 / 100	1093 ms	2204 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;
}

bool is_subseq(string a, string b) {
	int pos = 0;
	for (int i = 0; i < b.size(); i++) {
		while (pos < a.size() && b[i] != a[pos]) pos++;
		if (pos < a.size()) pos++;
		else return 0;
	}
	return 1;
}

string conv(int x) {
	string s = "";
	int bm = vec[x].second;
	for (int k = 0; k < vec[x].first; k++) {
		s.pb(bm % 3);
		bm /= 3;
	}
	return s;
}

int cst(int a, int b) {
	int lcp = 0;
	string sa = conv(a), sb = conv(b);
	for (int i = 0; i < min(sa.size(), sb.size()); i++)
		if (is_subseq(sa, sb.substr(0, i + 1))) lcp = i + 1;
		else break;
	return sb.size() - lcp;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0, p = 1; i <= 4; 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: In function 'bool is_subseq(std::string, std::string)':
lamp.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~
lamp.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   while (pos < a.size() && b[i] != a[pos]) pos++;
      |          ~~~~^~~~~~~~~~
lamp.cpp:51:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   if (pos < a.size()) pos++;
      |       ~~~~^~~~~~~~~~
lamp.cpp: In function 'int cst(int, int)':
lamp.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   70 |  for (int i = 0; i < min(sa.size(), sb.size()); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp: At global scope:
lamp.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main() {
      | ^~~~
lamp.cpp: In function 'int main()':
lamp.cpp:95: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]
   95 |   for (int b = 0; b < vec.size(); b++) {
      |                   ~~^~~~~~~~~~~~
lamp.cpp:97: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]
   97 |    for (int nb = 0; nb < vec.size(); nb++)
      |                     ~~~^~~~~~~~~~~~
lamp.cpp:98:72: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   98 |     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: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49