Submission #330651

#	Time	Username	Problem	Language	Result	Execution time	Memory
330651		limabeans	Lamps (JOI19_lamps)	C++17	6 / 100	451 ms	6632 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n;
int dp[1<<19];


int convert(string a) {
        int tmp = 0;
    for (char c: a) {
	tmp *= 2;
	tmp += (c-'0');
    }
    return tmp;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    string a, b;
    cin>>a;
    cin>>b;

    int start = convert(a);

    for (int i=0; i<1<<n; i++) {
	dp[i] = 1e9;
    }

    
    dp[start] = 0;
    queue<int> qq;
    qq.push(start);


    auto flip = [&](int mask, int l, int r) {
	int cover = (1<<(r-l+1)) - 1;
	cover <<= l;
	return mask^cover;
    };

    auto one = [&](int mask, int l, int r) {
	int cover = (1<<(r-l+1)) - 1;
	cover <<= l;
	return mask|cover;
    };


    auto zero = [&](int mask, int l, int r) {
	int cover = (1<<(r-l+1)) - 1;
	cover <<= l;
	return mask&(~cover);
    };

    while (qq.size()) {
	int mask = qq.front();
	qq.pop();

	for (int l=0; l<n; l++) {
	    for (int r=l; r<n; r++) {
		for (int nmask: {flip(mask,l,r), one(mask,l,r), zero(mask,l,r)}) {
		    if (dp[nmask]>1+dp[mask]) {
			dp[nmask] = 1+dp[mask];
			qq.push(nmask);
		    }
		}
	    }
	}
    }


    cout<<dp[convert(b)]<<endl;
    
    return 0;
}

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