Submission #631945

#	Time	Username	Problem	Language	Result	Execution time	Memory
631945		radal	Lamps (JOI19_lamps)	C++17	6 / 100	318 ms	21580 KiB

lamp

#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define pb push_back
#define X first
#define Y second
#define debug(x) cerr << #x << " : " << x << endl;
#define all(x) x.begin() , x.end()

using namespace std;

typedef pair<int,int> pll;
typedef long long ll;

constexpr int N = 3e5+10;

int d[N],pr[N][19],n,a,b;

void bfs(){
    queue<int> q;
    q.push(a);    
    d[a] = 0;
    while (!q.empty()){
        int v = q.front();
        if (v == b) break;
        q.pop();
        rep(l,0,n){
            rep(r,l,n){
                int s = pr[v][r],pw = (1 << (r+1))-(1 << l);
                if (l) s -= pr[v][l-1];
                if (d[v-s] > d[v]+1){
                    d[v-s] = d[v]+1;
                    q.push(v-s);
                }
                if (d[v+pw-s] > d[v]+1){
                    d[v+pw-s] = d[v]+1;
                    q.push(v+pw-s);
                }
                if (d[v+pw-2*s] > d[v]+1){
                    d[v+pw-2*s] = d[v]+1;
                    q.push(v+pw-2*s);
                }
            }
        }
    }
}
int main(){
    ios_base :: sync_with_stdio(0); cin.tie(0);
    memset(d,63,sizeof d);
    string s,t;
    cin >> n >> s >> t;
    rep(i,0,n){
        if (s[i] == '1') a += (1 << i);
        if (t[i] == '1') b += (1 << i);
    }
    int y = (1 << n);
    rep(i,1,y){
        rep(j,0,n){
            if (!j){
                if (i&1) pr[i][j] = 1;
                continue;
            }
            if (i&(1 << j)) pr[i][j] = pr[i][j-1]+(1 << j);
            else pr[i][j] = pr[i][j-1];
        }
    }
    bfs();
    cout << d[b];
}

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