Submission #422399

#	Time	Username	Problem	Language	Result	Execution time	Memory
422399		qwerasdfzxcl	Lamps (JOI19_lamps)	C++14	6 / 100	319 ms	7408 KiB

lamp

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int dist[1<<18];
bool visited[1<<18];

void convert(string &x, int &X){
    for (int i=0;i<(int)x.size();i++) if (x[i]=='1') X += (1<<i);
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    string x, y;
    cin >> n >> x >> y;
    int X = 0, Y = 0;
    convert(x, X); convert(y, Y);
    queue<int> q;
    q.push(X);
    visited[X] = 1;
    fill(dist, dist+(1<<18), 1e9);
    dist[X] = 0;

    int MX = (1<<n)-1;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for (int i=0;i<n;i++){
            int tmp = 0;
            for (int j=i;j<n;j++){
                tmp |= (1<<j);
                if (!visited[cur|tmp]){
                    visited[cur|tmp] = 1;
                    q.push(cur|tmp);
                    dist[cur|tmp] = dist[cur]+1;
                }
                if (!visited[cur^tmp]){
                    visited[cur^tmp] = 1;
                    q.push(cur^tmp);
                    dist[cur^tmp] = dist[cur]+1;
                }
                if (!visited[cur&(MX^tmp)]){
                    visited[cur&(MX^tmp)] = 1;
                    q.push(cur&(MX^tmp));
                    dist[cur&(MX^tmp)] = dist[cur]+1;
                }
            }
        }
    }
    cout << dist[Y];
    return 0;
}

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