Submission #1128177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128177		Alihan_8	Lamps (JOI19_lamps)	C++20	6 / 100	377 ms	4156 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

signed main(){
	int n; cin >> n;
	
	string a, b; cin >> a >> b;
	
	auto f = [&](string s){
		int cnt = 0;
		
		for ( auto &x: s ) cnt = cnt * 2 + x - '0';
		
		return cnt;
	};
	
	int x = f(a), y = f(b);
	
	vector <int> dp(1 << n, -1);
	
	dp[x] = 0;
	
	queue <int> q; q.push(x);
	
	while ( !q.empty() ){
		auto u = q.front();
		q.pop();
		
		for ( int i = 0; i < n; i++ ){
			vector <int> nxt = {u, u ,u};
			
			for ( int j = i; j < n; j++ ){
				int b = u >> j & 1;
				
				if ( b ) nxt[0] ^= 1 << j;
				else nxt[1] ^= 1 << j;
				
				nxt[2] ^= 1 << j;
				
				for ( auto &v: nxt ){
					if ( dp[v] == -1 ){
						dp[v] = dp[u] + 1;
						q.push(v);
					}
				}
			}
		}
	}
	
	cout << dp[y] << '\n';
}

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