Submission #873985

#	Time	Username	Problem	Language	Result	Execution time	Memory
873985		vjudge1	Lamps (JOI19_lamps)	C++17	6 / 100	951 ms	6828 KiB

lamp

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

typedef long long ll;
typedef array<int, 2> pii;

#define pb push_back
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()

const int N = 18;

int n, d[1 << N];
bool vis[1 << N];
string a, b;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> a >> b;
    int ia = 0, ib = 0;

    for (int i = 0; i < n; ++i) {
        if (a[i] == '1')
            ia += (1 << i);
        if (b[i] == '1')
            ib += (1 << i);
    }

    queue<int> q;
    q.push(ia);
    vis[ia] = 1;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        if (v == ib) {
            cout << d[v];
            return 0;
        }

        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                int u = v;
                for (int i = l; i <= r; ++i)
                    u |= (1 << i);
                if (!vis[u]) {
                    q.push(u);
                    vis[u] = 1;
                    d[u] = d[v] + 1;
                }

                u = v;
                for (int i = l; i <= r; ++i)
                    if (u & (1 << i))
                        u ^= (1 << i);
                if (!vis[u]) {
                    q.push(u);
                    vis[u] = 1;
                    d[u] = d[v] + 1;
                }

                u = v;
                for (int i = l; i <= r; ++i)
                    u ^= (1 << i);
                if (!vis[u]) {
                    q.push(u);
                    vis[u] = 1;
                    d[u] = d[v] + 1;
                }
            }
        }
    }

    return 0;
}

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