oj.uz

Submission #895689

# Submission time Handle Problem Language Result Execution time Memory
895689 2023-12-30T14:17:28 Z Unforgettablepl Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 1704 ms 65536 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<ll> point;
#define X real()
#define Y imag()
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const ll INF = 1e17;
const ll sqrtn = 440;
const ll modulo = 1e9+7;
const ll siz = 262144;
const ll hashp = 923981238;
const ll hashm = 932439994;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define int ll

map<string,int> memo;

int get(string &s){
    if(memo.count(s))return memo[s];
    for(char&x:s)if(x=='?'){
        x='1';
        int ans = get(s);
        x='0';
        ans += get(s);
        x='?';
        return memo[s]=ans;
    }
}

void solve() {
    int l,q;
    cin >> l >> q;
    for(int i=0;i<(1<<l);i++){
        char a;cin>>a;
        a-='0';
        memo[bitset<20>(i).to_string()] = a;
    }
    for(int i=1;i<=q;i++){
        string s;cin>>s;
        for(int x=0;x<20-l;x++)s.insert(s.begin(),'0');
        cout << get(s) << '\n';
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("cses.fi.txt","r",stdin);
//    freopen(".out","w",stdout);
//    int t;
//    cin >> t;
//    while(t--)
    solve();
}

Compilation message

snake_escaping.cpp: In function 'll get(std::string&)':
snake_escaping.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 11 ms 1732 KB Output is correct
6 Correct 7 ms 1288 KB Output is correct
7 Correct 7 ms 1356 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 5 ms 860 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 11 ms 1732 KB Output is correct
6 Correct 7 ms 1288 KB Output is correct
7 Correct 7 ms 1356 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 471 ms 15536 KB Output is correct
12 Correct 518 ms 15976 KB Output is correct
13 Correct 611 ms 15188 KB Output is correct
14 Correct 606 ms 15224 KB Output is correct
15 Correct 616 ms 17744 KB Output is correct
16 Correct 674 ms 17496 KB Output is correct
17 Correct 773 ms 20908 KB Output is correct
18 Correct 434 ms 16376 KB Output is correct
19 Correct 407 ms 13120 KB Output is correct
20 Correct 514 ms 15540 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 11 ms 1732 KB Output is correct
6 Correct 7 ms 1288 KB Output is correct
7 Correct 7 ms 1356 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 471 ms 15536 KB Output is correct
12 Correct 518 ms 15976 KB Output is correct
13 Correct 611 ms 15188 KB Output is correct
14 Correct 606 ms 15224 KB Output is correct
15 Correct 616 ms 17744 KB Output is correct
16 Correct 674 ms 17496 KB Output is correct
17 Correct 773 ms 20908 KB Output is correct
18 Correct 434 ms 16376 KB Output is correct
19 Correct 407 ms 13120 KB Output is correct
20 Correct 514 ms 15540 KB Output is correct
21 Correct 644 ms 22124 KB Output is correct
22 Correct 720 ms 24916 KB Output is correct
23 Correct 1704 ms 53448 KB Output is correct
24 Correct 1503 ms 46436 KB Output is correct
25 Correct 1644 ms 64540 KB Output is correct
26 Runtime error 1641 ms 65536 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 11 ms 1732 KB Output is correct
6 Correct 7 ms 1288 KB Output is correct
7 Correct 7 ms 1356 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 471 ms 15536 KB Output is correct
12 Correct 518 ms 15976 KB Output is correct
13 Correct 611 ms 15188 KB Output is correct
14 Correct 606 ms 15224 KB Output is correct
15 Correct 616 ms 17744 KB Output is correct
16 Correct 674 ms 17496 KB Output is correct
17 Correct 773 ms 20908 KB Output is correct
18 Correct 434 ms 16376 KB Output is correct
19 Correct 407 ms 13120 KB Output is correct
20 Correct 514 ms 15540 KB Output is correct
21 Correct 644 ms 22124 KB Output is correct
22 Correct 720 ms 24916 KB Output is correct
23 Correct 1704 ms 53448 KB Output is correct
24 Correct 1503 ms 46436 KB Output is correct
25 Correct 1644 ms 64540 KB Output is correct
26 Runtime error 1641 ms 65536 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -