oj.uz

Submission #135193

# Submission time Handle Problem Language Result Execution time Memory
135193 2019-07-23T19:29:46 Z duality Snake Escaping (JOI18_snake_escaping) C++11
100 / 100
 1642 ms 59028 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

int H = 7;
char S[(1 << 20)+1],T[21];
struct query { int m1,m2,i; };
query queries[1000000];
int pow3[21];
int ans[1000000];
int num[1594323];
int sum[1594323];
int main() {
    int i,j;
    int L,Q;
    scanf("%d %d %s",&L,&Q,S);
    H = min(H,L);
    for (i = 0; i < Q; i++) {
        scanf("%s",T),queries[i].i = i;
        reverse(T,T+H),reverse(T+H,T+L);
        for (j = 0; j < H; j++) {
            if (T[j] == '0') queries[i].m1 |= (1 << (2*j));
            else if (T[j] == '1') queries[i].m1 |= (1 << (2*j+1));
            else queries[i].m1 |= (1 << (2*j)) | (1 << (2*j+1));
        }
        int p = 1;
        for (j = H; j < L; j++) {
            if (T[j] == '1') queries[i].m2 += p;
            else if (T[j] == '?') queries[i].m2 += 2*p;
            p *= 3;
        }
    }

    int k;
    pow3[0] = 1;
    for (i = 1; i <= L; i++) pow3[i] = pow3[i-1]*3;
    for (i = 0; i < pow3[L-H]; i++) {
        int n = i;
        num[i] = -1;
        for (j = 0; j < L-H; j++) {
            if ((n % 3) == 2) num[i] = j;
            n /= 3;
        }
    }
    for (i = 0; i < (1 << H); i++) {
        for (j = 0; j < (1 << (L-H)); j++) {
            int c = 0;
            for (k = 0; k < L-H; k++) {
                if (j & (1 << k)) c += pow3[k];
            }
            sum[c] = S[j+i*(1 << (L-H))]-'0';
        }
        for (j = 0; j < pow3[L-H]; j++) {
            if (num[j] != -1) sum[j] = sum[j-pow3[num[j]]]+sum[j-2*pow3[num[j]]];
        }
        int m = 0;
        for (j = 0; j < H; j++) {
            if (i & (1 << j)) m |= (1 << (2*j+1));
            else m |= (1 << (2*j));
        }
        for (j = 0; j < Q; j++) {
            if ((queries[j].m1 & m) == m) ans[queries[j].i] += sum[queries[j].m2];
        }
    }
    for (i = 0; i < Q; i++) printf("%d\n",ans[i]);

    return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %s",&L,&Q,S);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",T),queries[i].i = i;
         ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 638 ms 20000 KB Output is correct
12 Correct 671 ms 19616 KB Output is correct
13 Correct 524 ms 19452 KB Output is correct
14 Correct 534 ms 19320 KB Output is correct
15 Correct 715 ms 20240 KB Output is correct
16 Correct 583 ms 19548 KB Output is correct
17 Correct 576 ms 19576 KB Output is correct
18 Correct 642 ms 21372 KB Output is correct
19 Correct 424 ms 18188 KB Output is correct
20 Correct 690 ms 20028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 638 ms 20000 KB Output is correct
12 Correct 671 ms 19616 KB Output is correct
13 Correct 524 ms 19452 KB Output is correct
14 Correct 534 ms 19320 KB Output is correct
15 Correct 715 ms 20240 KB Output is correct
16 Correct 583 ms 19548 KB Output is correct
17 Correct 576 ms 19576 KB Output is correct
18 Correct 642 ms 21372 KB Output is correct
19 Correct 424 ms 18188 KB Output is correct
20 Correct 690 ms 20028 KB Output is correct
21 Correct 722 ms 20364 KB Output is correct
22 Correct 695 ms 20600 KB Output is correct
23 Correct 564 ms 19448 KB Output is correct
24 Correct 605 ms 19340 KB Output is correct
25 Correct 811 ms 21292 KB Output is correct
26 Correct 643 ms 19748 KB Output is correct
27 Correct 625 ms 19864 KB Output is correct
28 Correct 674 ms 22280 KB Output is correct
29 Correct 473 ms 18260 KB Output is correct
30 Correct 700 ms 20448 KB Output is correct
31 Correct 660 ms 20344 KB Output is correct
32 Correct 620 ms 20344 KB Output is correct
33 Correct 506 ms 19124 KB Output is correct
34 Correct 588 ms 19448 KB Output is correct
35 Correct 618 ms 19912 KB Output is correct
36 Correct 362 ms 18296 KB Output is correct
37 Correct 657 ms 20276 KB Output is correct
38 Correct 469 ms 18260 KB Output is correct
39 Correct 576 ms 19376 KB Output is correct
40 Correct 675 ms 19248 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 507 ms 14916 KB Output is correct
12 Correct 511 ms 15024 KB Output is correct
13 Correct 513 ms 14888 KB Output is correct
14 Correct 520 ms 14912 KB Output is correct
15 Correct 520 ms 14968 KB Output is correct
16 Correct 516 ms 14840 KB Output is correct
17 Correct 510 ms 14844 KB Output is correct
18 Correct 504 ms 15096 KB Output is correct
19 Correct 499 ms 14768 KB Output is correct
20 Correct 507 ms 14936 KB Output is correct
21 Correct 510 ms 14968 KB Output is correct
22 Correct 527 ms 14788 KB Output is correct
23 Correct 529 ms 14840 KB Output is correct
24 Correct 507 ms 14840 KB Output is correct
25 Correct 517 ms 14824 KB Output is correct
26 Correct 504 ms 14812 KB Output is correct
27 Correct 511 ms 14940 KB Output is correct
28 Correct 500 ms 14756 KB Output is correct
29 Correct 505 ms 14824 KB Output is correct
30 Correct 504 ms 14840 KB Output is correct
31 Correct 502 ms 14840 KB Output is correct
32 Correct 516 ms 14840 KB Output is correct
33 Correct 514 ms 14920 KB Output is correct
34 Correct 497 ms 14780 KB Output is correct
35 Correct 516 ms 14840 KB Output is correct
36 Correct 512 ms 14840 KB Output is correct
37 Correct 526 ms 14840 KB Output is correct
38 Correct 512 ms 14840 KB Output is correct
39 Correct 510 ms 14840 KB Output is correct
40 Correct 512 ms 14840 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 638 ms 20000 KB Output is correct
12 Correct 671 ms 19616 KB Output is correct
13 Correct 524 ms 19452 KB Output is correct
14 Correct 534 ms 19320 KB Output is correct
15 Correct 715 ms 20240 KB Output is correct
16 Correct 583 ms 19548 KB Output is correct
17 Correct 576 ms 19576 KB Output is correct
18 Correct 642 ms 21372 KB Output is correct
19 Correct 424 ms 18188 KB Output is correct
20 Correct 690 ms 20028 KB Output is correct
21 Correct 722 ms 20364 KB Output is correct
22 Correct 695 ms 20600 KB Output is correct
23 Correct 564 ms 19448 KB Output is correct
24 Correct 605 ms 19340 KB Output is correct
25 Correct 811 ms 21292 KB Output is correct
26 Correct 643 ms 19748 KB Output is correct
27 Correct 625 ms 19864 KB Output is correct
28 Correct 674 ms 22280 KB Output is correct
29 Correct 473 ms 18260 KB Output is correct
30 Correct 700 ms 20448 KB Output is correct
31 Correct 660 ms 20344 KB Output is correct
32 Correct 620 ms 20344 KB Output is correct
33 Correct 506 ms 19124 KB Output is correct
34 Correct 588 ms 19448 KB Output is correct
35 Correct 618 ms 19912 KB Output is correct
36 Correct 362 ms 18296 KB Output is correct
37 Correct 657 ms 20276 KB Output is correct
38 Correct 469 ms 18260 KB Output is correct
39 Correct 576 ms 19376 KB Output is correct
40 Correct 675 ms 19248 KB Output is correct
41 Correct 507 ms 14916 KB Output is correct
42 Correct 511 ms 15024 KB Output is correct
43 Correct 513 ms 14888 KB Output is correct
44 Correct 520 ms 14912 KB Output is correct
45 Correct 520 ms 14968 KB Output is correct
46 Correct 516 ms 14840 KB Output is correct
47 Correct 510 ms 14844 KB Output is correct
48 Correct 504 ms 15096 KB Output is correct
49 Correct 499 ms 14768 KB Output is correct
50 Correct 507 ms 14936 KB Output is correct
51 Correct 510 ms 14968 KB Output is correct
52 Correct 527 ms 14788 KB Output is correct
53 Correct 529 ms 14840 KB Output is correct
54 Correct 507 ms 14840 KB Output is correct
55 Correct 517 ms 14824 KB Output is correct
56 Correct 504 ms 14812 KB Output is correct
57 Correct 511 ms 14940 KB Output is correct
58 Correct 500 ms 14756 KB Output is correct
59 Correct 505 ms 14824 KB Output is correct
60 Correct 504 ms 14840 KB Output is correct
61 Correct 502 ms 14840 KB Output is correct
62 Correct 516 ms 14840 KB Output is correct
63 Correct 514 ms 14920 KB Output is correct
64 Correct 497 ms 14780 KB Output is correct
65 Correct 516 ms 14840 KB Output is correct
66 Correct 512 ms 14840 KB Output is correct
67 Correct 526 ms 14840 KB Output is correct
68 Correct 512 ms 14840 KB Output is correct
69 Correct 510 ms 14840 KB Output is correct
70 Correct 512 ms 14840 KB Output is correct
71 Correct 1314 ms 34568 KB Output is correct
72 Correct 1390 ms 56156 KB Output is correct
73 Correct 1317 ms 54776 KB Output is correct
74 Correct 1417 ms 55160 KB Output is correct
75 Correct 1642 ms 57100 KB Output is correct
76 Correct 1409 ms 55396 KB Output is correct
77 Correct 1504 ms 55320 KB Output is correct
78 Correct 1232 ms 59028 KB Output is correct
79 Correct 1142 ms 52968 KB Output is correct
80 Correct 1375 ms 56324 KB Output is correct
81 Correct 1495 ms 56180 KB Output is correct
82 Correct 1379 ms 55028 KB Output is correct
83 Correct 1184 ms 54120 KB Output is correct
84 Correct 1328 ms 55120 KB Output is correct
85 Correct 1537 ms 55140 KB Output is correct
86 Correct 946 ms 53112 KB Output is correct
87 Correct 1359 ms 56020 KB Output is correct
88 Correct 1165 ms 52972 KB Output is correct
89 Correct 1340 ms 54740 KB Output is correct
90 Correct 1394 ms 55016 KB Output is correct
91 Correct 1164 ms 54252 KB Output is correct
92 Correct 1398 ms 55432 KB Output is correct
93 Correct 1495 ms 55348 KB Output is correct
94 Correct 1038 ms 53052 KB Output is correct
95 Correct 1539 ms 55140 KB Output is correct
96 Correct 1458 ms 55132 KB Output is correct
97 Correct 1491 ms 55148 KB Output is correct
98 Correct 1503 ms 55180 KB Output is correct
99 Correct 1495 ms 55128 KB Output is correct
100 Correct 1590 ms 55132 KB Output is correct