Submission #231948

#	Time	Username	Problem	Language	Result	Execution time	Memory
231948		oolimry	Lamps (JOI19_lamps)	C++14	100 / 100	126 ms	4812 KiB

lamp

#include <bits/stdc++.h>
#define SKIP 0
#define OFF 1
#define ON 2
#define SKIPXOR 3
#define OFFXOR 4
#define ONXOR 5
#define oper int
using namespace std;

int dist(oper a, oper b){
	int ans = 0;
	///If the skip/off/on is different, and b is not skip
	if(a % 3 != b % 3 && b % 3 != 0) ans++;
	///if XOR is taken
	if(a <= 2 && b >= 3) ans++;
	return ans;
}

int conv(int state, oper o){
	switch(o){
		case SKIP: return state;
		case OFF: return 0;
		case ON: return 1;
		case SKIPXOR: return state^1;
		case OFFXOR: return 1;
		case ONXOR: return 0;
		default: return -1;
	}
}

bitset<1000005> A;
bitset<1000005> B;

int pre[6];
int dp[6];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	string SA, SB;
	cin >> SA >> SB;
	
	for(int i = 0;i < n;i++){
		A[i] = (SA[i] == '1');
		B[i] = (SB[i] == '1');
	}
	
	fill(dp,dp+6,10234567); dp[0] = 0;
	
	oper operations[6] = {SKIP, OFF, ON, SKIPXOR, OFFXOR, ONXOR};
	
	for(int i = 0;i < n;i++){
		swap(dp, pre);
		fill(dp,dp+6,10234567);
		
		for(oper curOp : operations){
			if(conv(A[i], curOp) != B[i]) continue;
			
			for(oper preOp : operations){
				dp[curOp] = min(dp[curOp], pre[preOp] + dist(preOp, curOp));
			}	
		}
	}
	
	cout << min({dp[0],dp[1],dp[2],dp[3],dp[4],dp[5]});
}

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