oj.uz

Submission #888187

# Submission time Handle Problem Language Result Execution time Memory
888187 2023-12-16T09:56:49 Z Unforgettablepl Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 578 ms 13716 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = INT64_MAX;

int arr[1024];

int ask(string &a,int perm){
    int idx = 0;
    for(int x=0;x<a.size();x++){
        if(a[x]=='1')idx|=(1<<x);
        else if(a[x]=='?'){idx|=((perm&1)<<x);perm>>=1;}
    }
    return arr[idx];
}

int32_t main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int L,q;
    cin >> L >> q;
    for(int i=0;i<(1<<L);i++){
        char a;cin>>a;a-='0';
        arr[i]=a;
    }
    map<string,int> memo;
    for (int i = 0; i < q; i++) {
        string a;cin>>a;
        reverse(a.begin(), a.end());
        if(memo.count(a)){cout<<memo[a]<<'\n';continue;}
        int n = count(a.begin(), a.end(),'?');
        int ans = 0;
        for(int perm = 0;perm<(1<<n);perm++){
            ans+=ask(a,perm);
        }
        cout << ans << '\n';
        memo[a]=ans;
    }
}

Compilation message

snake_escaping.cpp: In function 'long long int ask(std::string&, long long int)':
snake_escaping.cpp:11:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int x=0;x<a.size();x++){
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 251 ms 4436 KB Output is correct
12 Correct 342 ms 4232 KB Output is correct
13 Correct 465 ms 3924 KB Output is correct
14 Correct 404 ms 3708 KB Output is correct
15 Correct 409 ms 4692 KB Output is correct
16 Correct 493 ms 4752 KB Output is correct
17 Correct 578 ms 8272 KB Output is correct
18 Correct 146 ms 12120 KB Output is correct
19 Correct 252 ms 12116 KB Output is correct
20 Correct 357 ms 13716 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 251 ms 4436 KB Output is correct
12 Correct 342 ms 4232 KB Output is correct
13 Correct 465 ms 3924 KB Output is correct
14 Correct 404 ms 3708 KB Output is correct
15 Correct 409 ms 4692 KB Output is correct
16 Correct 493 ms 4752 KB Output is correct
17 Correct 578 ms 8272 KB Output is correct
18 Correct 146 ms 12120 KB Output is correct
19 Correct 252 ms 12116 KB Output is correct
20 Correct 357 ms 13716 KB Output is correct
21 Runtime error 1 ms 604 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 251 ms 4436 KB Output is correct
12 Correct 342 ms 4232 KB Output is correct
13 Correct 465 ms 3924 KB Output is correct
14 Correct 404 ms 3708 KB Output is correct
15 Correct 409 ms 4692 KB Output is correct
16 Correct 493 ms 4752 KB Output is correct
17 Correct 578 ms 8272 KB Output is correct
18 Correct 146 ms 12120 KB Output is correct
19 Correct 252 ms 12116 KB Output is correct
20 Correct 357 ms 13716 KB Output is correct
21 Runtime error 1 ms 604 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -