oj.uz

Submission #422399

# Submission time Handle Problem Language Result Execution time Memory
422399 2021-06-10T05:44:08 Z qwerasdfzxcl Lamps (JOI19_lamps) C++14
6 / 100
 319 ms 7408 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1348 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 250 ms 1988 KB Output is correct
9 Correct 319 ms 2008 KB Output is correct
10 Correct 70 ms 1784 KB Output is correct
11 Correct 79 ms 1668 KB Output is correct
12 Correct 170 ms 1996 KB Output is correct
13 Correct 70 ms 1752 KB Output is correct
14 Correct 168 ms 1988 KB Output is correct
15 Correct 71 ms 1728 KB Output is correct
16 Correct 161 ms 2016 KB Output is correct
17 Correct 74 ms 1736 KB Output is correct
18 Correct 259 ms 2088 KB Output is correct
19 Correct 72 ms 1656 KB Output is correct
20 Correct 185 ms 2088 KB Output is correct
21 Correct 69 ms 1636 KB Output is correct
22 Correct 168 ms 2120 KB Output is correct
23 Correct 71 ms 1720 KB Output is correct
24 Correct 179 ms 1996 KB Output is correct
25 Correct 77 ms 1716 KB Output is correct
26 Correct 171 ms 2128 KB Output is correct
27 Correct 72 ms 1712 KB Output is correct
28 Correct 29 ms 1484 KB Output is correct
29 Correct 162 ms 2040 KB Output is correct
30 Correct 93 ms 1712 KB Output is correct
31 Correct 29 ms 1484 KB Output is correct
32 Correct 166 ms 2056 KB Output is correct
33 Correct 69 ms 1700 KB Output is correct
34 Correct 32 ms 1528 KB Output is correct

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1348 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 250 ms 1988 KB Output is correct
9 Correct 319 ms 2008 KB Output is correct
10 Correct 70 ms 1784 KB Output is correct
11 Correct 79 ms 1668 KB Output is correct
12 Correct 170 ms 1996 KB Output is correct
13 Correct 70 ms 1752 KB Output is correct
14 Correct 168 ms 1988 KB Output is correct
15 Correct 71 ms 1728 KB Output is correct
16 Correct 161 ms 2016 KB Output is correct
17 Correct 74 ms 1736 KB Output is correct
18 Correct 259 ms 2088 KB Output is correct
19 Correct 72 ms 1656 KB Output is correct
20 Correct 185 ms 2088 KB Output is correct
21 Correct 69 ms 1636 KB Output is correct
22 Correct 168 ms 2120 KB Output is correct
23 Correct 71 ms 1720 KB Output is correct
24 Correct 179 ms 1996 KB Output is correct
25 Correct 77 ms 1716 KB Output is correct
26 Correct 171 ms 2128 KB Output is correct
27 Correct 72 ms 1712 KB Output is correct
28 Correct 29 ms 1484 KB Output is correct
29 Correct 162 ms 2040 KB Output is correct
30 Correct 93 ms 1712 KB Output is correct
31 Correct 29 ms 1484 KB Output is correct
32 Correct 166 ms 2056 KB Output is correct
33 Correct 69 ms 1700 KB Output is correct
34 Correct 32 ms 1528 KB Output is correct
35 Runtime error 2 ms 2508 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1340 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Runtime error 13 ms 7408 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1348 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 250 ms 1988 KB Output is correct
9 Correct 319 ms 2008 KB Output is correct
10 Correct 70 ms 1784 KB Output is correct
11 Correct 79 ms 1668 KB Output is correct
12 Correct 170 ms 1996 KB Output is correct
13 Correct 70 ms 1752 KB Output is correct
14 Correct 168 ms 1988 KB Output is correct
15 Correct 71 ms 1728 KB Output is correct
16 Correct 161 ms 2016 KB Output is correct
17 Correct 74 ms 1736 KB Output is correct
18 Correct 259 ms 2088 KB Output is correct
19 Correct 72 ms 1656 KB Output is correct
20 Correct 185 ms 2088 KB Output is correct
21 Correct 69 ms 1636 KB Output is correct
22 Correct 168 ms 2120 KB Output is correct
23 Correct 71 ms 1720 KB Output is correct
24 Correct 179 ms 1996 KB Output is correct
25 Correct 77 ms 1716 KB Output is correct
26 Correct 171 ms 2128 KB Output is correct
27 Correct 72 ms 1712 KB Output is correct
28 Correct 29 ms 1484 KB Output is correct
29 Correct 162 ms 2040 KB Output is correct
30 Correct 93 ms 1712 KB Output is correct
31 Correct 29 ms 1484 KB Output is correct
32 Correct 166 ms 2056 KB Output is correct
33 Correct 69 ms 1700 KB Output is correct
34 Correct 32 ms 1528 KB Output is correct
35 Runtime error 2 ms 2508 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -