Submission #792539

#	Time	Username	Problem	Language	Result	Execution time	Memory
792539		vjudge1	Lamps (JOI19_lamps)	C++17	0 / 100	312 ms	262144 KiB

lamp

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int len;
int s, t;

const int N = (1 << 19);

int get_num(string s) {
    int res = 0;
    for(int i = (int)s.size() - 1, pw = 1; i >= 0; i--, pw *= 2) {
        if(s[i] == '1') res += pw;
    }
    return res;
}
vector<int> g1, g2;
int dist[N];
vector<bool> vis(N);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> len;
    string s0, t0;
    cin >> s0 >> t0;
    s = get_num(s0), t = get_num(t0);
    for(int i = 0; i < len; i++) {
        int x = 0;
        for(int j = i; j < len; j++) {
            x |= (1 << j);
            g1.push_back(x);
            g2.push_back((((1 << len) - 1) ^ x));
        }
    }
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int cur = q.front();
        if(cur == t) break;
        q.pop();
        for(int c : g1) {
            int to = (cur | c);
            if(!vis[to]) q.push(to), dist[to] = dist[cur] + 1, vis[to] = 1;
            to = (cur ^ c);
            if(!vis[to]) q.push(to), dist[to] = dist[cur] + 1, vis[to] = 1;
        }
        for(int c : g2) {
            int to = (cur & c);
            if(!vis[to]) q.push(to), dist[to] = dist[cur] + 1, vis[to] = 1;
        }
    }
    cout << dist[t];
    return 0;
}

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