oj.uz

Submission #719229

# Submission time Handle Problem Language Result Execution time Memory
719229 2023-04-05T16:35:51 Z ssense Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1867 ms 39308 KB 
#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize("Ofast")
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
//#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);}int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}//mesanu

int n, q;
string s;

int answer_C(string t, int qm)
{
    vector<int> pos;
    int base = 0;
    for(int i = 0; i < n; i++)
    {
        if(t[i] == '?')
        {
            pos.pb(i);
        }
        if(t[i] == '1')
        {
            base+=1<<i;
        }
    }
    int sum = 0;
    for(int i = 0; i < 1<<qm; i++)
    {
        int now = base;
        for(int j = 0; j < pos.size(); j++)
        {
            if(i & (1<<j))
            {
                now+=1<<pos[j];
            }
        }
        sum+=(s[now]-'0');
    }
    return sum;
}

int sub[(1<<20)+5];
int super[(1<<20)+5];

int answer_B(string t)
{
    vector<int> pos;
    int base = 0;
    for(int i = 0; i < n; i++)
    {
        if(t[i] == '1')
        {
            pos.pb(i);
        }
        if(t[i] == '?')
        {
            base+=1<<i;
        }
    }
    int sum = 0;
    int sz = pos.size();
    for(int mask = (1<<sz)-1; mask >= 0; mask--)
    {
        int now = base;
        for(int i = 0; i < pos.size(); i++)
        {
            if(mask & (1<<i))
            {
                now+=1<<pos[i];
            }
        }
        sum+=sub[now]*power(-1, sz-__builtin_popcount(mask), MOD);
    }
    return sum;
}

int answer_A(string t)
{
    vector<int> pos;
    int base = 0;
    for(int i = 0; i < n; i++)
    {
        if(t[i] == '0')
        {
            pos.pb(i);
        }
        if(t[i] == '1')
        {
            base+=1<<i;
        }
    }
    int sum = 0;
    int sz = pos.size();
    for(int mask = 0; mask < 1<<sz; mask++)
    {
        int now = base;
        for(int i = 0; i < pos.size(); i++)
        {
            if(mask & (1<<i))
            {
                now+=1<<pos[i];
            }
        }
        sum+=super[now]*power(-1, __builtin_popcount(mask), MOD);
    }
    return sum;
}

void solve()
{
    cin >> n >> q;
    cin >> s;
    for(int i = 0; i < 1<<n; i++)
    {
        sub[i] = (s[i]-'0');
        super[i] = (s[i]-'0');
    }
    for(int i = 0; i < n; i++)
    {
        for(int mask = 0; mask < 1<< n; mask++)
        {
            if(mask & 1<<i)
            {
                sub[mask]+=sub[mask^(1<<i)];
            }
        }
    }
    for(int i = n-1; i >= 0; i--)
    {
        for(int mask = (1<<n)-1; mask >= 0; mask--)
        {
            if(!(mask&(1<<i)))
            {
                super[mask]+=super[mask^(1<<i)];
            }
        }
    }
    while(q--)
    {
        string t;
        cin >> t;
        reverse(all(t));
        int qm = 0, ones = 0, zeros = 0;
        for(int i = 0; i < n; i++)
        {
            if(t[i] == '?'){qm++;}
            if(t[i] == '1'){ones++;}
            if(t[i] == '0'){zeros++;}
        }
        //cout << answer_A(t) << endl;
        if(ones == min({qm, ones, zeros}))
        {
            cout << answer_B(t) << endl;
        }
        else if(qm == min({qm, ones, zeros}))
        {
            cout << answer_C(t, qm) << endl;
        }
        else
        {
            cout << answer_A(t) << endl;
        }
    }
}

int32_t main(){
    startt
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
/*
3 5
12345678
000
0??
1?0
?11
???
*/

Compilation message

snake_escaping.cpp: In function 'int answer_C(std::string, int)':
snake_escaping.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j = 0; j < pos.size(); j++)
      |                        ~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'int answer_B(std::string)':
snake_escaping.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i = 0; i < pos.size(); i++)
      |                        ~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'int answer_A(std::string)':
snake_escaping.cpp:112:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int i = 0; i < pos.size(); i++)
      |                        ~~^~~~~~~~~~~~

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 340 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 340 KB Output is correct
9 Correct 1 ms 340 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 340 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 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 254 ms 4296 KB Output is correct
12 Correct 259 ms 3968 KB Output is correct
13 Correct 360 ms 3220 KB Output is correct
14 Correct 468 ms 3220 KB Output is correct
15 Correct 330 ms 4224 KB Output is correct
16 Correct 419 ms 3416 KB Output is correct
17 Correct 406 ms 3376 KB Output is correct
18 Correct 180 ms 5324 KB Output is correct
19 Correct 228 ms 2240 KB Output is correct
20 Correct 269 ms 3896 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 340 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 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 254 ms 4296 KB Output is correct
12 Correct 259 ms 3968 KB Output is correct
13 Correct 360 ms 3220 KB Output is correct
14 Correct 468 ms 3220 KB Output is correct
15 Correct 330 ms 4224 KB Output is correct
16 Correct 419 ms 3416 KB Output is correct
17 Correct 406 ms 3376 KB Output is correct
18 Correct 180 ms 5324 KB Output is correct
19 Correct 228 ms 2240 KB Output is correct
20 Correct 269 ms 3896 KB Output is correct
21 Correct 280 ms 4300 KB Output is correct
22 Correct 309 ms 4672 KB Output is correct
23 Correct 456 ms 3524 KB Output is correct
24 Correct 597 ms 3440 KB Output is correct
25 Correct 398 ms 5544 KB Output is correct
26 Correct 561 ms 3976 KB Output is correct
27 Correct 513 ms 3876 KB Output is correct
28 Correct 186 ms 6544 KB Output is correct
29 Correct 267 ms 2380 KB Output is correct
30 Correct 313 ms 4520 KB Output is correct
31 Correct 483 ms 4380 KB Output is correct
32 Correct 621 ms 4424 KB Output is correct
33 Correct 374 ms 3304 KB Output is correct
34 Correct 543 ms 3436 KB Output is correct
35 Correct 517 ms 3848 KB Output is correct
36 Correct 199 ms 2380 KB Output is correct
37 Correct 272 ms 4296 KB Output is correct
38 Correct 315 ms 2384 KB Output is correct
39 Correct 461 ms 3616 KB Output is correct
40 Correct 516 ms 3460 KB Output is correct

Subtask #4
53.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 340 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 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 59 ms 9860 KB Output is correct
12 Correct 62 ms 9932 KB Output is correct
13 Correct 81 ms 10056 KB Output is correct
14 Correct 126 ms 9796 KB Output is correct
15 Correct 74 ms 9872 KB Output is correct
16 Correct 125 ms 9824 KB Output is correct
17 Correct 104 ms 9788 KB Output is correct
18 Correct 60 ms 10012 KB Output is correct
19 Correct 58 ms 9736 KB Output is correct
20 Correct 58 ms 9896 KB Output is correct
21 Correct 77 ms 9832 KB Output is correct
22 Correct 135 ms 9796 KB Output is correct
23 Correct 63 ms 9808 KB Output is correct
24 Correct 105 ms 9900 KB Output is correct
25 Correct 102 ms 9784 KB Output is correct
26 Correct 52 ms 9772 KB Output is correct
27 Correct 59 ms 9836 KB Output is correct
28 Correct 58 ms 9724 KB Output is correct
29 Correct 72 ms 9804 KB Output is correct
30 Correct 91 ms 9836 KB Output is correct
31 Correct 66 ms 9772 KB Output is correct
32 Correct 109 ms 9796 KB Output is correct
33 Correct 100 ms 9800 KB Output is correct
34 Correct 56 ms 9796 KB Output is correct
35 Correct 86 ms 9800 KB Output is correct
36 Correct 89 ms 9836 KB Output is correct
37 Correct 87 ms 9804 KB Output is correct
38 Correct 93 ms 9836 KB Output is correct
39 Correct 86 ms 9772 KB Output is correct
40 Correct 88 ms 9812 KB Output is correct

Subtask #5
25.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 340 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 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 254 ms 4296 KB Output is correct
12 Correct 259 ms 3968 KB Output is correct
13 Correct 360 ms 3220 KB Output is correct
14 Correct 468 ms 3220 KB Output is correct
15 Correct 330 ms 4224 KB Output is correct
16 Correct 419 ms 3416 KB Output is correct
17 Correct 406 ms 3376 KB Output is correct
18 Correct 180 ms 5324 KB Output is correct
19 Correct 228 ms 2240 KB Output is correct
20 Correct 269 ms 3896 KB Output is correct
21 Correct 280 ms 4300 KB Output is correct
22 Correct 309 ms 4672 KB Output is correct
23 Correct 456 ms 3524 KB Output is correct
24 Correct 597 ms 3440 KB Output is correct
25 Correct 398 ms 5544 KB Output is correct
26 Correct 561 ms 3976 KB Output is correct
27 Correct 513 ms 3876 KB Output is correct
28 Correct 186 ms 6544 KB Output is correct
29 Correct 267 ms 2380 KB Output is correct
30 Correct 313 ms 4520 KB Output is correct
31 Correct 483 ms 4380 KB Output is correct
32 Correct 621 ms 4424 KB Output is correct
33 Correct 374 ms 3304 KB Output is correct
34 Correct 543 ms 3436 KB Output is correct
35 Correct 517 ms 3848 KB Output is correct
36 Correct 199 ms 2380 KB Output is correct
37 Correct 272 ms 4296 KB Output is correct
38 Correct 315 ms 2384 KB Output is correct
39 Correct 461 ms 3616 KB Output is correct
40 Correct 516 ms 3460 KB Output is correct
41 Correct 59 ms 9860 KB Output is correct
42 Correct 62 ms 9932 KB Output is correct
43 Correct 81 ms 10056 KB Output is correct
44 Correct 126 ms 9796 KB Output is correct
45 Correct 74 ms 9872 KB Output is correct
46 Correct 125 ms 9824 KB Output is correct
47 Correct 104 ms 9788 KB Output is correct
48 Correct 60 ms 10012 KB Output is correct
49 Correct 58 ms 9736 KB Output is correct
50 Correct 58 ms 9896 KB Output is correct
51 Correct 77 ms 9832 KB Output is correct
52 Correct 135 ms 9796 KB Output is correct
53 Correct 63 ms 9808 KB Output is correct
54 Correct 105 ms 9900 KB Output is correct
55 Correct 102 ms 9784 KB Output is correct
56 Correct 52 ms 9772 KB Output is correct
57 Correct 59 ms 9836 KB Output is correct
58 Correct 58 ms 9724 KB Output is correct
59 Correct 72 ms 9804 KB Output is correct
60 Correct 91 ms 9836 KB Output is correct
61 Correct 66 ms 9772 KB Output is correct
62 Correct 109 ms 9796 KB Output is correct
63 Correct 100 ms 9800 KB Output is correct
64 Correct 56 ms 9796 KB Output is correct
65 Correct 86 ms 9800 KB Output is correct
66 Correct 89 ms 9836 KB Output is correct
67 Correct 87 ms 9804 KB Output is correct
68 Correct 93 ms 9836 KB Output is correct
69 Correct 86 ms 9772 KB Output is correct
70 Correct 88 ms 9812 KB Output is correct
71 Correct 495 ms 14612 KB Output is correct
72 Correct 469 ms 14792 KB Output is correct
73 Correct 809 ms 13244 KB Output is correct
74 Correct 1773 ms 13912 KB Output is correct
75 Correct 555 ms 15660 KB Output is correct
76 Correct 1547 ms 20328 KB Output is correct
77 Correct 1299 ms 35456 KB Output is correct
78 Correct 334 ms 39308 KB Output is correct
79 Correct 428 ms 33360 KB Output is correct
80 Correct 441 ms 36332 KB Output is correct
81 Correct 903 ms 36296 KB Output is correct
82 Correct 1867 ms 35260 KB Output is correct
83 Correct 543 ms 34400 KB Output is correct
84 Correct 1547 ms 35352 KB Output is correct
85 Correct 1375 ms 35436 KB Output is correct
86 Correct 320 ms 33172 KB Output is correct
87 Correct 512 ms 36216 KB Output is correct
88 Correct 464 ms 33328 KB Output is correct
89 Correct 749 ms 34796 KB Output is correct
90 Correct 1071 ms 35436 KB Output is correct
91 Correct 536 ms 34380 KB Output is correct
92 Correct 1579 ms 35764 KB Output is correct
93 Correct 1235 ms 35436 KB Output is correct
94 Correct 331 ms 33152 KB Output is correct
95 Correct 1004 ms 35240 KB Output is correct
96 Correct 1046 ms 35296 KB Output is correct
97 Correct 991 ms 35240 KB Output is correct
98 Correct 1032 ms 35260 KB Output is correct
99 Correct 1033 ms 35396 KB Output is correct
100 Correct 1028 ms 35340 KB Output is correct