oj.uz

Submission #792539

# Submission time Handle Problem Language Result Execution time Memory
792539 2023-07-25T06:39:48 Z vjudge1 Lamps (JOI19_lamps) C++17
0 / 100
 312 ms 262144 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Runtime error 312 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -