Submission #1184794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184794		irmuun	Lamps (JOI19_lamps)	C++20	0 / 100	180 ms	327680 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    if(n<=18){
        vector<int>g[1<<n];
        vector<int>d(1<<n,1e9);
        for(int i=0;i<(1<<n);i++){
            for(int l=0;l<n;l++){
                int num=0;
                for(int r=l;r<n;r++){
                    num|=(1<<r);
                    g[i].pb(i^num);
                    g[i].pb(i&(~num));
                    g[i].pb(i|num);
                }
            }
        }
        int a=0,b=0;
        for(int i=0;i<n;i++){
            if(s[i]=='1') a|=(1<<i);
            if(t[i]=='1') b|=(1<<i);
        }
        queue<int>q;
        q.push(a);
        d[a]=0;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int y:g[x]){
                if(d[x]+1<d[y]){
                    d[y]=d[x]+1;
                    q.push(y);
                }
            }
        }
        cout<<d[b];
        return 0;
    }
}

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