oj.uz

Submission #895691

# Submission time Handle Problem Language Result Execution time Memory
895691 2023-12-30T14:22:10 Z Unforgettablepl Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 64648 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<13>(i).to_string()] = a;
    }
    for(int i=1;i<=q;i++){
        string s;cin>>s;
        for(int x=0;x<13-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 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
7 Correct 7 ms 980 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 836 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
7 Correct 7 ms 980 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 358 ms 4692 KB Output is correct
12 Correct 407 ms 4528 KB Output is correct
13 Correct 503 ms 4268 KB Output is correct
14 Correct 503 ms 4272 KB Output is correct
15 Correct 498 ms 6228 KB Output is correct
16 Correct 599 ms 5804 KB Output is correct
17 Correct 666 ms 8060 KB Output is correct
18 Correct 306 ms 5496 KB Output is correct
19 Correct 291 ms 2388 KB Output is correct
20 Correct 422 ms 4556 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
7 Correct 7 ms 980 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 358 ms 4692 KB Output is correct
12 Correct 407 ms 4528 KB Output is correct
13 Correct 503 ms 4268 KB Output is correct
14 Correct 503 ms 4272 KB Output is correct
15 Correct 498 ms 6228 KB Output is correct
16 Correct 599 ms 5804 KB Output is correct
17 Correct 666 ms 8060 KB Output is correct
18 Correct 306 ms 5496 KB Output is correct
19 Correct 291 ms 2388 KB Output is correct
20 Correct 422 ms 4556 KB Output is correct
21 Correct 539 ms 7324 KB Output is correct
22 Correct 582 ms 9616 KB Output is correct
23 Correct 1454 ms 29508 KB Output is correct
24 Correct 1230 ms 24404 KB Output is correct
25 Correct 1510 ms 38048 KB Output is correct
26 Execution timed out 2009 ms 64648 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
7 Correct 7 ms 980 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Runtime error 168 ms 2980 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 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1084 KB Output is correct
7 Correct 7 ms 980 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 836 KB Output is correct
11 Correct 358 ms 4692 KB Output is correct
12 Correct 407 ms 4528 KB Output is correct
13 Correct 503 ms 4268 KB Output is correct
14 Correct 503 ms 4272 KB Output is correct
15 Correct 498 ms 6228 KB Output is correct
16 Correct 599 ms 5804 KB Output is correct
17 Correct 666 ms 8060 KB Output is correct
18 Correct 306 ms 5496 KB Output is correct
19 Correct 291 ms 2388 KB Output is correct
20 Correct 422 ms 4556 KB Output is correct
21 Correct 539 ms 7324 KB Output is correct
22 Correct 582 ms 9616 KB Output is correct
23 Correct 1454 ms 29508 KB Output is correct
24 Correct 1230 ms 24404 KB Output is correct
25 Correct 1510 ms 38048 KB Output is correct
26 Execution timed out 2009 ms 64648 KB Time limit exceeded
27 Halted 0 ms 0 KB -