Submission #554630

#	Time	Username	Problem	Language	Result	Execution time	Memory
554630		pavement	Lamps (JOI19_lamps)	C++17	6 / 100	1109 ms	205712 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, mem[1000005][16];
bool A[1000005], B[1000005];
char C;

// 0: 
// 1: 0
// 2: 1
// 3: T
// 4: 01
// 5: 10
// 6: 0T
// 7: T0
// 8: 1T
// 9: T1
// 10: 01T
// 11: 0T1
// 12: 10T
// 13: 1T0
// 14: T01
// 15: T10

string S[] = {"", "0", "1", "T", "01", "10", "0T", "T0", "1T", "T1", "01T", "0T1", "10T", "1T0", "T01", "T10"};

bool apply(bool x, int b) {
	if (b == 0) return x;
	else if (b == 1 || b == 5 || b == 7 || b == 8 || b == 10 || b == 13 || b == 15) return 0;
	else if (b == 2 || b == 4 || b == 6 || b == 9 || b == 11 || b == 12 || b == 14) return 1;
	else 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;
}

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

int dp(int n, int b) {
	if (n == N + 1) return 0;
	if (mem[n][b] != -1) return mem[n][b];
	int ret = LLONG_MAX;
	for (int nb = 0; nb < 16; nb++)
		if (apply(A[n], nb) == B[n]) ret = min(ret, dp(n + 1, nb) + cst(b, nb));
	return mem[n][b] = ret;
}

main() {
	memset(mem, -1, sizeof mem);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	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';
	}
	cout << dp(1, 0) << '\n';
}

Compilation message (stderr)

lamp.cpp: In function 'bool is_subseq(std::string, std::string)':
lamp.cpp:61:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~
lamp.cpp:62:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   while (pos < a.size() && b[i] != a[pos]) pos++;
      |          ~~~~^~~~~~~~~~
lamp.cpp:63:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if (pos < a.size()) pos++;
      |       ~~~~^~~~~~~~~~
lamp.cpp: In function 'long long int cst(long long int, long long int)':
lamp.cpp:71:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
   71 |  for (int i = 0; i < min(S[a].size(), S[b].size()); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp: At global scope:
lamp.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main() {
      | ^~~~

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