oj.uz

Submission #522224

# Submission time Handle Problem Language Result Execution time Memory
522224 2022-02-04T08:22:31 Z Monarchuwu Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 381 ms 26200 KB 
#include<iostream>
#include<algorithm>
#include<string>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 2e6 + 10;
int l, q;
string s;

int pw3[13 + 1], a[N];
void prep() {
    pw3[0] = 1;
    for (int i = 1; i <= l; ++i)
        pw3[i] = pw3[i - 1] * 3;

    for (int i = 0, msk; i < s.size(); ++i) {
        msk = 0;
        for (int j = 0; j < l; ++j)
            if (i >> j & 1) msk += pw3[j];
        a[msk] = s[i] ^ 48;
    }

    for (int j = 0; j < l; ++j)
        for (int msk = 0; msk < pw3[l]; ++msk)
            if (msk / pw3[j] % 3 == 2)
                a[msk] += a[msk - pw3[j]] + a[msk - pw3[j] * 2];
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> l >> q >> s;
    prep();

    while (q--) {
        string t; cin >> t;
        int msk(0);
        for (char c : t) {
            msk *= 3;
            if (c == '1') ++msk;
            else if (c == '?') msk += 2;
        }
        cout << a[msk] << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message

snake_escaping.cpp: In function 'void prep()':
snake_escaping.cpp:18:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0, msk; i < s.size(); ++i) {
      |                          ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 552 KB Output is correct
6 Correct 5 ms 556 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 5 ms 460 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 552 KB Output is correct
6 Correct 5 ms 556 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 221 ms 4548 KB Output is correct
12 Correct 161 ms 4208 KB Output is correct
13 Correct 173 ms 3396 KB Output is correct
14 Correct 188 ms 3452 KB Output is correct
15 Correct 166 ms 4524 KB Output is correct
16 Correct 177 ms 3636 KB Output is correct
17 Correct 194 ms 3680 KB Output is correct
18 Correct 159 ms 5452 KB Output is correct
19 Correct 187 ms 2620 KB Output is correct
20 Correct 186 ms 4132 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 552 KB Output is correct
6 Correct 5 ms 556 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 221 ms 4548 KB Output is correct
12 Correct 161 ms 4208 KB Output is correct
13 Correct 173 ms 3396 KB Output is correct
14 Correct 188 ms 3452 KB Output is correct
15 Correct 166 ms 4524 KB Output is correct
16 Correct 177 ms 3636 KB Output is correct
17 Correct 194 ms 3680 KB Output is correct
18 Correct 159 ms 5452 KB Output is correct
19 Correct 187 ms 2620 KB Output is correct
20 Correct 186 ms 4132 KB Output is correct
21 Correct 350 ms 10580 KB Output is correct
22 Correct 316 ms 24520 KB Output is correct
23 Correct 358 ms 23332 KB Output is correct
24 Correct 347 ms 23184 KB Output is correct
25 Correct 351 ms 25232 KB Output is correct
26 Correct 354 ms 23828 KB Output is correct
27 Correct 372 ms 23748 KB Output is correct
28 Correct 298 ms 26200 KB Output is correct
29 Correct 344 ms 22292 KB Output is correct
30 Correct 336 ms 24308 KB Output is correct
31 Correct 356 ms 24364 KB Output is correct
32 Correct 330 ms 24260 KB Output is correct
33 Correct 333 ms 23108 KB Output is correct
34 Correct 363 ms 23204 KB Output is correct
35 Correct 381 ms 23692 KB Output is correct
36 Correct 282 ms 22160 KB Output is correct
37 Correct 286 ms 24260 KB Output is correct
38 Correct 337 ms 22212 KB Output is correct
39 Correct 350 ms 23436 KB Output is correct
40 Correct 357 ms 23192 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 552 KB Output is correct
6 Correct 5 ms 556 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Runtime error 4 ms 2800 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 552 KB Output is correct
6 Correct 5 ms 556 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 221 ms 4548 KB Output is correct
12 Correct 161 ms 4208 KB Output is correct
13 Correct 173 ms 3396 KB Output is correct
14 Correct 188 ms 3452 KB Output is correct
15 Correct 166 ms 4524 KB Output is correct
16 Correct 177 ms 3636 KB Output is correct
17 Correct 194 ms 3680 KB Output is correct
18 Correct 159 ms 5452 KB Output is correct
19 Correct 187 ms 2620 KB Output is correct
20 Correct 186 ms 4132 KB Output is correct
21 Correct 350 ms 10580 KB Output is correct
22 Correct 316 ms 24520 KB Output is correct
23 Correct 358 ms 23332 KB Output is correct
24 Correct 347 ms 23184 KB Output is correct
25 Correct 351 ms 25232 KB Output is correct
26 Correct 354 ms 23828 KB Output is correct
27 Correct 372 ms 23748 KB Output is correct
28 Correct 298 ms 26200 KB Output is correct
29 Correct 344 ms 22292 KB Output is correct
30 Correct 336 ms 24308 KB Output is correct
31 Correct 356 ms 24364 KB Output is correct
32 Correct 330 ms 24260 KB Output is correct
33 Correct 333 ms 23108 KB Output is correct
34 Correct 363 ms 23204 KB Output is correct
35 Correct 381 ms 23692 KB Output is correct
36 Correct 282 ms 22160 KB Output is correct
37 Correct 286 ms 24260 KB Output is correct
38 Correct 337 ms 22212 KB Output is correct
39 Correct 350 ms 23436 KB Output is correct
40 Correct 357 ms 23192 KB Output is correct
41 Runtime error 4 ms 2800 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -