Submission #1259429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259429		mingga	Lamps (JOI19_lamps)	C++20	4 / 100	37 ms	26852 KiB

lamp

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 1e6 + 7;
int n, f[N][2][3];
string s;
bool a[N], b[N];

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n;
	cin >> s;
	for(int i = 1; i <= n; i++) a[i] = (s[i - 1] - 48);
	cin >> s;
	for(int i = 1; i <= n; i++) b[i] = (s[i - 1] - 48);
	for(int j = 0; j < 3; j++) {
		for(int k = 0; k < 2; k++) {
			f[0][j][k] = inf;
		}
	}
	f[0][0][0] = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			for(int k = 0; k < 2; k++) {
				f[i][j][k] = inf;
				int cur = a[i];
				if(j == 1) cur = 0;
				if(j == 2) cur = 1;
				if(k) cur ^= 1;
				if(cur != b[i]) continue;
				for(int tj = 0; tj < 3; tj++) {
					for(int tk = 0; tk < 2; tk++) {
						f[i][j][k] = min(f[i][j][k], f[i - 1][tj][tk] + (j and j != tj) + (k and !tk));
					}
				}
			}
		}
	}
	int ans = inf;
	for(int j = 0; j < 3; j++) {
		for(int k = 0; k < 2; k++) {
			ans = min(ans, f[n][j][k]);
		}
	}
	cout << ans << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:24:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:25:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:49:93: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   49 |                                                 f[i][j][k] = min(f[i][j][k], f[i - 1][tj][tk] + (j and j != tj) + (k and !tk));
      |                                                                              ~~~~~~~~~~~~~~~^
lamp.cpp:47:52: note: within this loop
   47 |                                 for(int tj = 0; tj < 3; tj++) {
      |                                                 ~~~^~~
lamp.cpp:34:36: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   34 |                         f[0][j][k] = inf;
      |                         ~~~~~~~~~~~^~~~~
lamp.cpp:32:26: note: within this loop
   32 |         for(int j = 0; j < 3; j++) {
      |                        ~~^~~

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