oj.uz

Submission #792549

# Submission time Handle Problem Language Result Execution time Memory
792549 2023-07-25T06:48:54 Z vjudge1 Lamps (JOI19_lamps) C++17
6 / 100
 131 ms 4368 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;
    if(len <= 18) {

        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);
        vis[s] = 1;
        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;
    }
    if(s0 == string(len, '0')) {
        int ans = 0;
        for(int i = 0; i < len - 1; i++)
            ans += (t0[i] != t0[0] && t0[i + 1] == t0[0]);
        ans += (t0[len - 1] != t0[0]);
        cout << ans;
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 396 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 131 ms 1820 KB Output is correct
9 Correct 131 ms 1804 KB Output is correct
10 Correct 56 ms 1088 KB Output is correct
11 Correct 58 ms 1100 KB Output is correct
12 Correct 11 ms 1748 KB Output is correct
13 Correct 49 ms 1184 KB Output is correct
14 Correct 26 ms 1852 KB Output is correct
15 Correct 65 ms 1176 KB Output is correct
16 Correct 64 ms 1924 KB Output is correct
17 Correct 46 ms 1176 KB Output is correct
18 Correct 26 ms 1860 KB Output is correct
19 Correct 10 ms 1068 KB Output is correct
20 Correct 75 ms 1912 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 22 ms 1884 KB Output is correct
23 Correct 31 ms 1140 KB Output is correct
24 Correct 4 ms 1492 KB Output is correct
25 Correct 4 ms 980 KB Output is correct
26 Correct 62 ms 1872 KB Output is correct
27 Correct 19 ms 1144 KB Output is correct
28 Correct 7 ms 788 KB Output is correct
29 Correct 88 ms 1856 KB Output is correct
30 Correct 41 ms 1140 KB Output is correct
31 Correct 3 ms 724 KB Output is correct
32 Correct 29 ms 1836 KB Output is correct
33 Correct 48 ms 1140 KB Output is correct
34 Correct 18 ms 784 KB Output is correct

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 396 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 131 ms 1820 KB Output is correct
9 Correct 131 ms 1804 KB Output is correct
10 Correct 56 ms 1088 KB Output is correct
11 Correct 58 ms 1100 KB Output is correct
12 Correct 11 ms 1748 KB Output is correct
13 Correct 49 ms 1184 KB Output is correct
14 Correct 26 ms 1852 KB Output is correct
15 Correct 65 ms 1176 KB Output is correct
16 Correct 64 ms 1924 KB Output is correct
17 Correct 46 ms 1176 KB Output is correct
18 Correct 26 ms 1860 KB Output is correct
19 Correct 10 ms 1068 KB Output is correct
20 Correct 75 ms 1912 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 22 ms 1884 KB Output is correct
23 Correct 31 ms 1140 KB Output is correct
24 Correct 4 ms 1492 KB Output is correct
25 Correct 4 ms 980 KB Output is correct
26 Correct 62 ms 1872 KB Output is correct
27 Correct 19 ms 1144 KB Output is correct
28 Correct 7 ms 788 KB Output is correct
29 Correct 88 ms 1856 KB Output is correct
30 Correct 41 ms 1140 KB Output is correct
31 Correct 3 ms 724 KB Output is correct
32 Correct 29 ms 1836 KB Output is correct
33 Correct 48 ms 1140 KB Output is correct
34 Correct 18 ms 784 KB Output is correct
35 Incorrect 1 ms 340 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 9 ms 4272 KB Output is correct
8 Correct 10 ms 4256 KB Output is correct
9 Incorrect 10 ms 4368 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 396 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 131 ms 1820 KB Output is correct
9 Correct 131 ms 1804 KB Output is correct
10 Correct 56 ms 1088 KB Output is correct
11 Correct 58 ms 1100 KB Output is correct
12 Correct 11 ms 1748 KB Output is correct
13 Correct 49 ms 1184 KB Output is correct
14 Correct 26 ms 1852 KB Output is correct
15 Correct 65 ms 1176 KB Output is correct
16 Correct 64 ms 1924 KB Output is correct
17 Correct 46 ms 1176 KB Output is correct
18 Correct 26 ms 1860 KB Output is correct
19 Correct 10 ms 1068 KB Output is correct
20 Correct 75 ms 1912 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 22 ms 1884 KB Output is correct
23 Correct 31 ms 1140 KB Output is correct
24 Correct 4 ms 1492 KB Output is correct
25 Correct 4 ms 980 KB Output is correct
26 Correct 62 ms 1872 KB Output is correct
27 Correct 19 ms 1144 KB Output is correct
28 Correct 7 ms 788 KB Output is correct
29 Correct 88 ms 1856 KB Output is correct
30 Correct 41 ms 1140 KB Output is correct
31 Correct 3 ms 724 KB Output is correct
32 Correct 29 ms 1836 KB Output is correct
33 Correct 48 ms 1140 KB Output is correct
34 Correct 18 ms 784 KB Output is correct
35 Incorrect 1 ms 340 KB Output isn't correct
36 Halted 0 ms 0 KB -