Untitled

mail@pastecode.io avatar
unknown
c_cpp
21 days ago
1.5 kB
4
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1<<15 + 10;

int visited[maxn];
int dist[maxn];

int main()
{
    int n, m;
    cin >> n >> m;

    int st = 0;
    for(int i = 0, x; i < n; i++) {
        cin >> x;
        st = st * 2 + x;
    }

    int p[20];
    for(int i = 0, idx = 0, now = 0, x; i < m; i++) {
        cin >> x;
        while(x--) p[idx++] = now;
        now ^= 1;
    }

    int ed1 = 0, ed2 = 0;
    for(int i = 0; i < n; i++) {
        ed1 = ed1 * 2 + p[i];
        ed2 = ed2 * 2 + (p[i] ^ 1);
    }

    memset(dist, 0x3f, sizeof dist);

    dist[st] = 0;

    queue<int> Q;
    Q.push(st);

    while(!Q.empty()) {
        int now = Q.front();
        Q.pop();

        // cout << now << " e ashlam" << endl;

        if(now == ed1 || now == ed2) break;

        for(int i = 0; i < n-1; i++) {
            int here = now;

            int last = (here & (1 << i)) > 0;
            int ager = (here & (1 << (i + 1))) > 0;

            if(last == ager) continue;

            here |= (1 << i);
            here |= (1 << (i + 1));
            here ^= (1 << i);
            here ^= (1 << (i + 1));

            here ^= (ager << i);
            here ^= (last << (i + 1));

            if(!visited[here]) {
                visited[here] = 1;
                Q.push(here);

                dist[here] = dist[now] + 1;
            }
        }
    }

    cout << min(dist[ed1], dist[ed2]) << endl;
    

    return 0;
}
Leave a Comment