oj.uz

Submission #1048170

# Submission time Handle Problem Language Result Execution time Memory
1048170 2024-08-08T03:42:00 Z khanhtb Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 237 ms 17244 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const int mod = 998244353; 
const ll inf = 2e18;
const int B = 320;
const int N = 2e6+8;
int n,q,a[N];
int sub[N],sup[N];
void solve(){
    cin >> n >> q;
    for(int i = 0; i < 1<<n; i++){
        char c;cin >> c;
        a[i] = c-'0';
        sub[i] = sup[i] = a[i];
    }
    for(int i = 0; i < n; i++){
        for(int mask = 0; mask < 1<<n; mask++){
            if(mask>>i&1) sub[mask] += sub[mask^(1<<i)];
            else sup[mask] += sup[mask^(1<<i)];
        }
    }
    while(q--){
        string t;cin >> t;
        int mask[3] = {0};
        int cnt[3] = {0};
        reverse(all(t));
        for(int i = 0; i < t.size(); i++){
            int type;
            if(t[i] == '0') type = 0;
            else if(t[i] == '1') type = 1;
            else type = 2;
            cnt[type]++;
            mask[type] |= (1<<i);
        }
        int ans = 0;
        if(cnt[2] <= 7){
            ll ans = 0;
            for(int m = mask[2]; ; m = (m-1)&mask[2]){
                ans += a[mask[1]|m];
                if(m == 0) break;
            }
            cout << ans << '\n';
        }
        else if(cnt[1] <= 7){
            ll ans = 0;
            for(int m = mask[1]; ; m = (m-1)&mask[1]){
                if(__builtin_popcount(m)&1) ans -= sub[(m ^ mask[1]) | mask[2]];
                else ans += sub[(m ^ mask[1]) | mask[2]];
                if(m == 0) break;
            }
            cout << ans << '\n';
        }
        else{
            ll ans = 0;
            for(int m = mask[1]; ; m = (m-1)&mask[0]){
                if(__builtin_popcount(m)&1) ans -= sup[m | mask[1]];
                else ans += sup[m | mask[1]];
                if(m == 0) break;
            }
            cout << ans << '\n';
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }   
    ll T = 1;
    // cin >> T;
    for (ll i = 1; i <= T; i++) {
        solve();
        cout << '\n';
    }
}

Compilation message

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i = 0; i < t.size(); i++){
      |                        ~~^~~~~~~~~~
snake_escaping.cpp:48:13: warning: unused variable 'ans' [-Wunused-variable]
   48 |         int ans = 0;
      |             ^~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 123 ms 8508 KB Output is correct
12 Correct 154 ms 8020 KB Output is correct
13 Correct 121 ms 7252 KB Output is correct
14 Correct 147 ms 7504 KB Output is correct
15 Correct 155 ms 8392 KB Output is correct
16 Correct 127 ms 7508 KB Output is correct
17 Correct 139 ms 7548 KB Output is correct
18 Correct 95 ms 9556 KB Output is correct
19 Correct 111 ms 6484 KB Output is correct
20 Correct 139 ms 8076 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 123 ms 8508 KB Output is correct
12 Correct 154 ms 8020 KB Output is correct
13 Correct 121 ms 7252 KB Output is correct
14 Correct 147 ms 7504 KB Output is correct
15 Correct 155 ms 8392 KB Output is correct
16 Correct 127 ms 7508 KB Output is correct
17 Correct 139 ms 7548 KB Output is correct
18 Correct 95 ms 9556 KB Output is correct
19 Correct 111 ms 6484 KB Output is correct
20 Correct 139 ms 8076 KB Output is correct
21 Correct 237 ms 8348 KB Output is correct
22 Correct 194 ms 8552 KB Output is correct
23 Correct 151 ms 7656 KB Output is correct
24 Correct 140 ms 7592 KB Output is correct
25 Correct 130 ms 9448 KB Output is correct
26 Correct 162 ms 8284 KB Output is correct
27 Correct 162 ms 8016 KB Output is correct
28 Correct 112 ms 10536 KB Output is correct
29 Correct 120 ms 6352 KB Output is correct
30 Correct 183 ms 8708 KB Output is correct
31 Correct 189 ms 8392 KB Output is correct
32 Correct 149 ms 8532 KB Output is correct
33 Correct 141 ms 7424 KB Output is correct
34 Correct 133 ms 7464 KB Output is correct
35 Correct 158 ms 7816 KB Output is correct
36 Correct 98 ms 6484 KB Output is correct
37 Correct 172 ms 8488 KB Output is correct
38 Correct 128 ms 6480 KB Output is correct
39 Correct 131 ms 7760 KB Output is correct
40 Correct 127 ms 7428 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Incorrect 24 ms 17244 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 123 ms 8508 KB Output is correct
12 Correct 154 ms 8020 KB Output is correct
13 Correct 121 ms 7252 KB Output is correct
14 Correct 147 ms 7504 KB Output is correct
15 Correct 155 ms 8392 KB Output is correct
16 Correct 127 ms 7508 KB Output is correct
17 Correct 139 ms 7548 KB Output is correct
18 Correct 95 ms 9556 KB Output is correct
19 Correct 111 ms 6484 KB Output is correct
20 Correct 139 ms 8076 KB Output is correct
21 Correct 237 ms 8348 KB Output is correct
22 Correct 194 ms 8552 KB Output is correct
23 Correct 151 ms 7656 KB Output is correct
24 Correct 140 ms 7592 KB Output is correct
25 Correct 130 ms 9448 KB Output is correct
26 Correct 162 ms 8284 KB Output is correct
27 Correct 162 ms 8016 KB Output is correct
28 Correct 112 ms 10536 KB Output is correct
29 Correct 120 ms 6352 KB Output is correct
30 Correct 183 ms 8708 KB Output is correct
31 Correct 189 ms 8392 KB Output is correct
32 Correct 149 ms 8532 KB Output is correct
33 Correct 141 ms 7424 KB Output is correct
34 Correct 133 ms 7464 KB Output is correct
35 Correct 158 ms 7816 KB Output is correct
36 Correct 98 ms 6484 KB Output is correct
37 Correct 172 ms 8488 KB Output is correct
38 Correct 128 ms 6480 KB Output is correct
39 Correct 131 ms 7760 KB Output is correct
40 Correct 127 ms 7428 KB Output is correct
41 Incorrect 24 ms 17244 KB Output isn't correct
42 Halted 0 ms 0 KB -