제출 #231864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231864		oolimry	Lamps (JOI19_lamps)	C++14	0 / 100	15 ms	6612 KiB

lamp

#include <bits/stdc++.h>
#define BLACK '0'
#define WHITE '1'
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	string A, B;
	cin >> A >> B;
	
	int colour = B[0];
	vector<int> types;
	///0 - correct, 1 - all wrong, 2 - prefix wrong, 3 - suffix wrong, 4 - prefix & suffix wrong, 5 - rojak
	bool firstCorrect = (A[0] == B[0]);
	bool lastCorrect = false;
	int flip = 0;
	for(int i = 0;i < n;i++){
		
		if(i == n-1 || B[i] != B[i+1]){
			
			lastCorrect = (A[i] == colour);
			int type = 0;
			
			if(flip == 0){
				if(lastCorrect) type = 0;
				else type = 1;
			}
			else if(flip == 1){
				if(firstCorrect) type = 3;
				else type = 2;
			}
			else if(flip == 2){
				if(!firstCorrect && !lastCorrect) type = 4;
				else type = 5;
			}
			else type = 5;
			
			types.push_back(type);
			
			if(colour == WHITE) colour = BLACK;
			else colour = WHITE;
			
			flip = 0;
			if(i != n-1) firstCorrect = (A[i+1] == colour);
		}
		else if(A[i] != A[i+1]) flip++;
	}
	
	//for(int x : types) cout << x << " "; cout << "\n";
	
	auto backward = [&](int i){
		for(int j = i - 1;j >= 0;j--){
			if(types[j] == 0 || types[j] == 2) break;
			else if(types[j] == 1) types[j] = 0;
			else if(types[j] == 3) {types[j] = 0; break;}
			else if(types[j] == 4) {types[j] = 2; break;}
		}
	};
	
	auto forward = [&](int i){
		for(int j = i + 1;j < (int) types.size();j++){
			if(types[j] == 0 || types[j] == 3) break;
			else if(types[j] == 1) types[j] = 0;
			else if(types[j] == 2) {types[j] = 0; break;}
			else if(types[j] == 4) {types[j] = 3; break;}
		}
	};
	
	int ans = 0;
	while(true){
		bool has = false;
		for(int i = 0;i < n;i++){
			
			if(types[i] == 2 || types[i] == 1 || types[i] == 3){
				ans++;
				if(types[i] == 2 || types[i] == 1) backward(i);
				if(types[i] == 3 || types[i] == 1) forward(i);
				
				has = true;
				types[i] = 0;
			}
			
		}
		
		if(!has) break;
		
	
	}
	
	//cout << ans << "\n";
	
	for(int x : types){
		if(x != 0) ans++;
	}
	
	cout << ans << "\n";
}

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