oj.uz

Submission #679898

# Submission time Handle Problem Language Result Execution time Memory
679898 2023-01-09T15:51:36 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 2000 ms 19972 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const ll lg = 20;
 
int f1[(1 << lg) + 5];
int l, q;
string s;

void solve()
{
    cin >> l >> q;
    cin >> s;
    for(int i = 0; i < (1 << l); i++)
        f1[i] = s[i] - '0';
    
    for(int bit = 0; bit < l; bit++)
        for(int i = 0; i < (1 << l); i++)
            if (i >> bit & 1) f1[i ^ (1 << bit)] += f1[i];
            
    while(q--)
    {
        cin >> s;
        int mask0 = 0, mask1 = 0;
        for(int i = 0; i < l; i++)
        {
            if(s[i] == '1')
                mask1 |= (1 << (l - 1 - i));
            if(s[i] == '0')
                mask0 |= (1 << (l - 1 - i));
        }
        int res = f1[mask1], tmp = mask0;
        while(tmp)
        {
            int mul = (__builtin_popcount(tmp) & 1 ? -1 : 1);
            res += mul * f1[tmp + mask1];
            tmp = mask0 & (tmp - 1);
        }
        cout << res << '\n';
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Subtask #1
5.0 / 5.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 336 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 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.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 336 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 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 186 ms 14964 KB Output is correct
12 Correct 346 ms 14688 KB Output is correct
13 Correct 286 ms 13992 KB Output is correct
14 Correct 245 ms 14028 KB Output is correct
15 Correct 184 ms 15064 KB Output is correct
16 Correct 237 ms 14356 KB Output is correct
17 Correct 257 ms 14212 KB Output is correct
18 Correct 157 ms 16060 KB Output is correct
19 Correct 301 ms 12952 KB Output is correct
20 Correct 193 ms 14632 KB Output is correct

Subtask #3
10.0 / 10.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 336 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 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 186 ms 14964 KB Output is correct
12 Correct 346 ms 14688 KB Output is correct
13 Correct 286 ms 13992 KB Output is correct
14 Correct 245 ms 14028 KB Output is correct
15 Correct 184 ms 15064 KB Output is correct
16 Correct 237 ms 14356 KB Output is correct
17 Correct 257 ms 14212 KB Output is correct
18 Correct 157 ms 16060 KB Output is correct
19 Correct 301 ms 12952 KB Output is correct
20 Correct 193 ms 14632 KB Output is correct
21 Correct 210 ms 18072 KB Output is correct
22 Correct 798 ms 18104 KB Output is correct
23 Correct 393 ms 17228 KB Output is correct
24 Correct 299 ms 16972 KB Output is correct
25 Correct 214 ms 19060 KB Output is correct
26 Correct 287 ms 17620 KB Output is correct
27 Correct 430 ms 17492 KB Output is correct
28 Correct 196 ms 19972 KB Output is correct
29 Correct 419 ms 15964 KB Output is correct
30 Correct 227 ms 18216 KB Output is correct
31 Correct 254 ms 18004 KB Output is correct
32 Correct 255 ms 18092 KB Output is correct
33 Correct 230 ms 16940 KB Output is correct
34 Correct 321 ms 16976 KB Output is correct
35 Correct 345 ms 17620 KB Output is correct
36 Correct 146 ms 16076 KB Output is correct
37 Correct 565 ms 18044 KB Output is correct
38 Correct 815 ms 16040 KB Output is correct
39 Correct 263 ms 17296 KB Output is correct
40 Correct 290 ms 16952 KB Output is correct

Subtask #4
0 / 53.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 336 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 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 34 ms 7852 KB Output is correct
12 Correct 592 ms 7876 KB Output is correct
13 Correct 275 ms 7796 KB Output is correct
14 Correct 63 ms 7800 KB Output is correct
15 Correct 35 ms 7856 KB Output is correct
16 Correct 51 ms 7788 KB Output is correct
17 Correct 121 ms 7740 KB Output is correct
18 Correct 29 ms 7928 KB Output is correct
19 Correct 252 ms 7660 KB Output is correct
20 Correct 47 ms 7784 KB Output is correct
21 Correct 45 ms 7764 KB Output is correct
22 Correct 47 ms 7776 KB Output is correct
23 Correct 49 ms 7720 KB Output is correct
24 Correct 95 ms 7752 KB Output is correct
25 Correct 109 ms 7736 KB Output is correct
26 Correct 31 ms 7752 KB Output is correct
27 Correct 273 ms 7864 KB Output is correct
28 Correct 593 ms 7692 KB Output is correct
29 Correct 45 ms 7736 KB Output is correct
30 Correct 77 ms 7764 KB Output is correct
31 Correct 1830 ms 7700 KB Output is correct
32 Correct 125 ms 7716 KB Output is correct
33 Correct 147 ms 7708 KB Output is correct
34 Execution timed out 2077 ms 6768 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #5
0 / 25.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 336 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 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 186 ms 14964 KB Output is correct
12 Correct 346 ms 14688 KB Output is correct
13 Correct 286 ms 13992 KB Output is correct
14 Correct 245 ms 14028 KB Output is correct
15 Correct 184 ms 15064 KB Output is correct
16 Correct 237 ms 14356 KB Output is correct
17 Correct 257 ms 14212 KB Output is correct
18 Correct 157 ms 16060 KB Output is correct
19 Correct 301 ms 12952 KB Output is correct
20 Correct 193 ms 14632 KB Output is correct
21 Correct 210 ms 18072 KB Output is correct
22 Correct 798 ms 18104 KB Output is correct
23 Correct 393 ms 17228 KB Output is correct
24 Correct 299 ms 16972 KB Output is correct
25 Correct 214 ms 19060 KB Output is correct
26 Correct 287 ms 17620 KB Output is correct
27 Correct 430 ms 17492 KB Output is correct
28 Correct 196 ms 19972 KB Output is correct
29 Correct 419 ms 15964 KB Output is correct
30 Correct 227 ms 18216 KB Output is correct
31 Correct 254 ms 18004 KB Output is correct
32 Correct 255 ms 18092 KB Output is correct
33 Correct 230 ms 16940 KB Output is correct
34 Correct 321 ms 16976 KB Output is correct
35 Correct 345 ms 17620 KB Output is correct
36 Correct 146 ms 16076 KB Output is correct
37 Correct 565 ms 18044 KB Output is correct
38 Correct 815 ms 16040 KB Output is correct
39 Correct 263 ms 17296 KB Output is correct
40 Correct 290 ms 16952 KB Output is correct
41 Correct 34 ms 7852 KB Output is correct
42 Correct 592 ms 7876 KB Output is correct
43 Correct 275 ms 7796 KB Output is correct
44 Correct 63 ms 7800 KB Output is correct
45 Correct 35 ms 7856 KB Output is correct
46 Correct 51 ms 7788 KB Output is correct
47 Correct 121 ms 7740 KB Output is correct
48 Correct 29 ms 7928 KB Output is correct
49 Correct 252 ms 7660 KB Output is correct
50 Correct 47 ms 7784 KB Output is correct
51 Correct 45 ms 7764 KB Output is correct
52 Correct 47 ms 7776 KB Output is correct
53 Correct 49 ms 7720 KB Output is correct
54 Correct 95 ms 7752 KB Output is correct
55 Correct 109 ms 7736 KB Output is correct
56 Correct 31 ms 7752 KB Output is correct
57 Correct 273 ms 7864 KB Output is correct
58 Correct 593 ms 7692 KB Output is correct
59 Correct 45 ms 7736 KB Output is correct
60 Correct 77 ms 7764 KB Output is correct
61 Correct 1830 ms 7700 KB Output is correct
62 Correct 125 ms 7716 KB Output is correct
63 Correct 147 ms 7708 KB Output is correct
64 Execution timed out 2077 ms 6768 KB Time limit exceeded
65 Halted 0 ms 0 KB -