oj.uz

Submission #140502

# Submission time Handle Problem Language Result Execution time Memory
140502 2019-08-03T09:05:09 Z wasyl Snake Escaping (JOI18_snake_escaping) C++11
58 / 100
 2000 ms 20432 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int lax = 20, qax = 1e6, nax = (1 << lax);

int l, q, n, tab[nax], pre[3][nax];
string s;

int id(const char c)
{
    if (c == '?') return 2;
    return c - '0';
}

int rek(const int t, string& s, const int v)
{
    for (int i = v; i < l; ++i)
        if (id(s[i]) == t)
        {
            int res = 0;
            if (t == 2)
            {
                s[i] = '0';
                res += rek(t, s, i + 1);
                s[i] = '1';
                res += rek(t, s, i + 1);
                s[i] = '?';
                return res;
            }
            if (t == 0)
            {
                s[i] = '?';
                res += rek(t, s, i + 1);
                s[i] = '1';
                res -= rek(t, s, i + 1);
                s[i] = '0';
                return res;
            }
            if (t == 1)
            {
                s[i] = '?';
                res += rek(t, s, i + 1);
                s[i] = '0';
                res -= rek(t, s, i + 1);
                s[i] = '1';
                return res;
            }

        }
    int msk = 0;
    for (int i = 0; i < l; ++i)
    {
        if (s[i] == '0') continue;
        if (s[i] == '1' and t == 2)
            msk += (1 << i);
        if (s[i] == '?')
            msk += (1 << i);
    }
    //cerr << s << ' ' << msk << ' ' << pre[t][msk] << '\n';
    return pre[t][msk]; //spo
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> l >> q;
    n = (1 << l);

    cin >> s;

    for (int i = 0; i < n; ++i)
        tab[i] = s[i] - '0';

    for (int i = 0; i < n; ++i)
        pre[0][i] = tab[(n - 1) - i];
    for (int i = 0; i < n; ++i)
        pre[1][i] = tab[i];
    for (int i = 0; i < n; ++i)
        pre[2][i] = tab[i];

    for (int i = 0; i < l; ++i)
        for (int j = 0; j < n; ++j)
            if ((1 << i) & j)
                pre[0][j] += pre[0][j - (1 << i)],
                pre[1][j] += pre[1][j - (1 << i)];

    for (int i = 0; i < q; ++i)
    {
        string s; cin >> s;
        reverse(begin(s), end(s));
        int zl[2] = {0, 0};
        for (char c : s)
            if (c == '0' or c == '1')
            ++zl[c - '0'];
        if (zl[0] <= lax / 3)
            cout << rek(0, s, 0) << '\n';
        else if (zl[1] <= lax / 3)
            cout << rek(1, s, 0) << '\n';
        else if (l - zl[0] - zl[1] <= lax / 3)
            cout << rek(2, s, 0) << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 358 ms 15132 KB Output is correct
12 Execution timed out 2045 ms 14948 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 358 ms 15132 KB Output is correct
12 Execution timed out 2045 ms 14948 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 89 ms 20248 KB Output is correct
12 Correct 101 ms 20248 KB Output is correct
13 Correct 253 ms 20248 KB Output is correct
14 Correct 496 ms 20248 KB Output is correct
15 Correct 177 ms 20272 KB Output is correct
16 Correct 582 ms 20348 KB Output is correct
17 Correct 402 ms 20252 KB Output is correct
18 Correct 68 ms 20376 KB Output is correct
19 Correct 79 ms 20120 KB Output is correct
20 Correct 88 ms 20432 KB Output is correct
21 Correct 319 ms 20248 KB Output is correct
22 Correct 535 ms 20392 KB Output is correct
23 Correct 176 ms 20092 KB Output is correct
24 Correct 436 ms 20252 KB Output is correct
25 Correct 352 ms 20284 KB Output is correct
26 Correct 70 ms 20120 KB Output is correct
27 Correct 86 ms 20328 KB Output is correct
28 Correct 106 ms 19988 KB Output is correct
29 Correct 266 ms 20248 KB Output is correct
30 Correct 497 ms 20252 KB Output is correct
31 Correct 163 ms 20124 KB Output is correct
32 Correct 468 ms 20192 KB Output is correct
33 Correct 348 ms 20248 KB Output is correct
34 Correct 68 ms 20120 KB Output is correct
35 Correct 267 ms 20220 KB Output is correct
36 Correct 266 ms 20248 KB Output is correct
37 Correct 270 ms 20248 KB Output is correct
38 Correct 269 ms 20248 KB Output is correct
39 Correct 269 ms 20124 KB Output is correct
40 Correct 268 ms 20236 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 358 ms 15132 KB Output is correct
12 Execution timed out 2045 ms 14948 KB Time limit exceeded
13 Halted 0 ms 0 KB -