oj.uz

Submission #210497

# Submission time Handle Problem Language Result Execution time Memory
210497 2020-03-17T14:14:32 Z SamAnd Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1897 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 22, Q = 1000006, m = 13;

int n, qq;
char a[(1 << N)];

bool so(const char a[], const char b[])
{
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] != b[i])
            return a[i] < b[i];
    }
    return false;
}
struct ban
{
    int i;
    char u[N];
};
bool operator<(const ban& a, const ban& b)
{
    return so(a.u, b.u);
}
ban b[Q];

int* t[N];

int ans[Q];

void rec(int i, int x, int u)
{
    if (i == n + 1)
    {
        ans[b[u].i] += t[min(n, m)][x];
        return;
    }
    if (b[u].u[i] == '0')
        rec(i + 1, x, u);
    else if (b[u].u[i] == '1')
        rec(i + 1, x + (1 << (n - i)), u);
    else
    {
        rec(i + 1, x, u);
        rec(i + 1, x + (1 << (n - i)), u);
    }
}

int main()
{
    scanf("%d%d", &n, &qq);
    scanf(" %s", a);
    for (int i = 0; i < (1 << n); ++i)
        a[i] -= '0';
    for (int i = 0; i < qq; ++i)
    {
        b[i].i = i;
        scanf(" %s", (b[i].u + 1));
    }
    sort(b, b + qq);
    for (int j = 0; j <= n; ++j)
        t[j] = new int[(1 << (n - j))];
    for (int k = 0; k < (1 << n); ++k)
        t[0][k] = a[k];
    for (int i = 0; i < qq; ++i)
    {
        int s = m + 1;
        for (int j = 1; j <= min(n, m); ++j)
        {
            if (i == 0 || b[i].u[j] != b[i - 1].u[j])
            {
                s = j;
                break;
            }
        }
        for (int j = s; j <= min(n, m); ++j)
        {
            if (b[i].u[j] == '0')
            {
                for (int k = 0; k < (1 << (n - j)); ++k)
                {
                    t[j][k] = t[j - 1][k];
                }
            }
            else if (b[i].u[j] == '1')
            {
                for (int k = 0; k < (1 << (n - j)); ++k)
                {
                    t[j][k] = t[j - 1][k + (1 << (n - j))];
                }
            }
            else
            {
                for (int k = 0; k < (1 << (n - j)); ++k)
                {
                    t[j][k] = t[j - 1][k] + t[j - 1][k + (1 << (n - j))];
                }
            }
        }
        if (n <= m)
        {
            ans[b[i].i] = t[n][0];
            continue;
        }
        rec(m + 1, 0, i);
    }
    for (int i = 0; i < qq; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &qq);
     ~~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", a);
     ~~~~~^~~~~~~~~~
snake_escaping.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", (b[i].u + 1));
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 526 ms 36840 KB Output is correct
12 Correct 549 ms 36472 KB Output is correct
13 Correct 542 ms 35704 KB Output is correct
14 Correct 525 ms 35832 KB Output is correct
15 Correct 510 ms 36856 KB Output is correct
16 Correct 555 ms 35960 KB Output is correct
17 Correct 580 ms 35964 KB Output is correct
18 Correct 412 ms 37752 KB Output is correct
19 Correct 498 ms 34808 KB Output is correct
20 Correct 532 ms 37240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 526 ms 36840 KB Output is correct
12 Correct 549 ms 36472 KB Output is correct
13 Correct 542 ms 35704 KB Output is correct
14 Correct 525 ms 35832 KB Output is correct
15 Correct 510 ms 36856 KB Output is correct
16 Correct 555 ms 35960 KB Output is correct
17 Correct 580 ms 35964 KB Output is correct
18 Correct 412 ms 37752 KB Output is correct
19 Correct 498 ms 34808 KB Output is correct
20 Correct 532 ms 37240 KB Output is correct
21 Correct 569 ms 37624 KB Output is correct
22 Correct 618 ms 36984 KB Output is correct
23 Correct 651 ms 36216 KB Output is correct
24 Correct 616 ms 35832 KB Output is correct
25 Correct 613 ms 37880 KB Output is correct
26 Correct 660 ms 36984 KB Output is correct
27 Correct 695 ms 36984 KB Output is correct
28 Correct 483 ms 39544 KB Output is correct
29 Correct 598 ms 35572 KB Output is correct
30 Correct 597 ms 37624 KB Output is correct
31 Correct 642 ms 37624 KB Output is correct
32 Correct 624 ms 37624 KB Output is correct
33 Correct 598 ms 36472 KB Output is correct
34 Correct 698 ms 36612 KB Output is correct
35 Correct 747 ms 37772 KB Output is correct
36 Correct 545 ms 36876 KB Output is correct
37 Correct 619 ms 39064 KB Output is correct
38 Correct 793 ms 37028 KB Output is correct
39 Correct 680 ms 38524 KB Output is correct
40 Correct 631 ms 38392 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 76 ms 13432 KB Output is correct
12 Correct 79 ms 13432 KB Output is correct
13 Correct 244 ms 13412 KB Output is correct
14 Correct 296 ms 13432 KB Output is correct
15 Correct 199 ms 13560 KB Output is correct
16 Correct 295 ms 13432 KB Output is correct
17 Correct 299 ms 13432 KB Output is correct
18 Correct 103 ms 13688 KB Output is correct
19 Correct 66 ms 13304 KB Output is correct
20 Correct 80 ms 13432 KB Output is correct
21 Correct 266 ms 13432 KB Output is correct
22 Correct 295 ms 13428 KB Output is correct
23 Correct 177 ms 13432 KB Output is correct
24 Correct 290 ms 13432 KB Output is correct
25 Correct 296 ms 13436 KB Output is correct
26 Correct 44 ms 13304 KB Output is correct
27 Correct 76 ms 13432 KB Output is correct
28 Correct 71 ms 13304 KB Output is correct
29 Correct 252 ms 13432 KB Output is correct
30 Correct 289 ms 13432 KB Output is correct
31 Correct 173 ms 13432 KB Output is correct
32 Correct 296 ms 13432 KB Output is correct
33 Correct 298 ms 13436 KB Output is correct
34 Correct 44 ms 13304 KB Output is correct
35 Correct 265 ms 13432 KB Output is correct
36 Correct 276 ms 13432 KB Output is correct
37 Correct 272 ms 13432 KB Output is correct
38 Correct 269 ms 13432 KB Output is correct
39 Correct 267 ms 13460 KB Output is correct
40 Correct 270 ms 13432 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 526 ms 36840 KB Output is correct
12 Correct 549 ms 36472 KB Output is correct
13 Correct 542 ms 35704 KB Output is correct
14 Correct 525 ms 35832 KB Output is correct
15 Correct 510 ms 36856 KB Output is correct
16 Correct 555 ms 35960 KB Output is correct
17 Correct 580 ms 35964 KB Output is correct
18 Correct 412 ms 37752 KB Output is correct
19 Correct 498 ms 34808 KB Output is correct
20 Correct 532 ms 37240 KB Output is correct
21 Correct 569 ms 37624 KB Output is correct
22 Correct 618 ms 36984 KB Output is correct
23 Correct 651 ms 36216 KB Output is correct
24 Correct 616 ms 35832 KB Output is correct
25 Correct 613 ms 37880 KB Output is correct
26 Correct 660 ms 36984 KB Output is correct
27 Correct 695 ms 36984 KB Output is correct
28 Correct 483 ms 39544 KB Output is correct
29 Correct 598 ms 35572 KB Output is correct
30 Correct 597 ms 37624 KB Output is correct
31 Correct 642 ms 37624 KB Output is correct
32 Correct 624 ms 37624 KB Output is correct
33 Correct 598 ms 36472 KB Output is correct
34 Correct 698 ms 36612 KB Output is correct
35 Correct 747 ms 37772 KB Output is correct
36 Correct 545 ms 36876 KB Output is correct
37 Correct 619 ms 39064 KB Output is correct
38 Correct 793 ms 37028 KB Output is correct
39 Correct 680 ms 38524 KB Output is correct
40 Correct 631 ms 38392 KB Output is correct
41 Correct 76 ms 13432 KB Output is correct
42 Correct 79 ms 13432 KB Output is correct
43 Correct 244 ms 13412 KB Output is correct
44 Correct 296 ms 13432 KB Output is correct
45 Correct 199 ms 13560 KB Output is correct
46 Correct 295 ms 13432 KB Output is correct
47 Correct 299 ms 13432 KB Output is correct
48 Correct 103 ms 13688 KB Output is correct
49 Correct 66 ms 13304 KB Output is correct
50 Correct 80 ms 13432 KB Output is correct
51 Correct 266 ms 13432 KB Output is correct
52 Correct 295 ms 13428 KB Output is correct
53 Correct 177 ms 13432 KB Output is correct
54 Correct 290 ms 13432 KB Output is correct
55 Correct 296 ms 13436 KB Output is correct
56 Correct 44 ms 13304 KB Output is correct
57 Correct 76 ms 13432 KB Output is correct
58 Correct 71 ms 13304 KB Output is correct
59 Correct 252 ms 13432 KB Output is correct
60 Correct 289 ms 13432 KB Output is correct
61 Correct 173 ms 13432 KB Output is correct
62 Correct 296 ms 13432 KB Output is correct
63 Correct 298 ms 13436 KB Output is correct
64 Correct 44 ms 13304 KB Output is correct
65 Correct 265 ms 13432 KB Output is correct
66 Correct 276 ms 13432 KB Output is correct
67 Correct 272 ms 13432 KB Output is correct
68 Correct 269 ms 13432 KB Output is correct
69 Correct 267 ms 13460 KB Output is correct
70 Correct 270 ms 13432 KB Output is correct
71 Correct 1010 ms 65536 KB Output is correct
72 Correct 1081 ms 65536 KB Output is correct
73 Correct 1352 ms 65536 KB Output is correct
74 Correct 1447 ms 65536 KB Output is correct
75 Correct 1371 ms 65536 KB Output is correct
76 Correct 1528 ms 65536 KB Output is correct
77 Correct 1566 ms 65536 KB Output is correct
78 Correct 1897 ms 65536 KB Output is correct
79 Correct 845 ms 64584 KB Output is correct
80 Correct 1073 ms 65536 KB Output is correct
81 Correct 1451 ms 65536 KB Output is correct
82 Correct 1482 ms 65536 KB Output is correct
83 Correct 1102 ms 65536 KB Output is correct
84 Correct 1508 ms 65536 KB Output is correct
85 Correct 1571 ms 65536 KB Output is correct
86 Correct 638 ms 64504 KB Output is correct
87 Correct 982 ms 65536 KB Output is correct
88 Correct 886 ms 64472 KB Output is correct
89 Correct 1356 ms 65536 KB Output is correct
90 Correct 1443 ms 65536 KB Output is correct
91 Correct 1089 ms 65536 KB Output is correct
92 Correct 1541 ms 65536 KB Output is correct
93 Correct 1577 ms 65536 KB Output is correct
94 Correct 651 ms 64460 KB Output is correct
95 Correct 1518 ms 65536 KB Output is correct
96 Correct 1535 ms 65536 KB Output is correct
97 Correct 1517 ms 65536 KB Output is correct
98 Correct 1513 ms 65536 KB Output is correct
99 Correct 1516 ms 65536 KB Output is correct
100 Correct 1501 ms 65536 KB Output is correct