답안 #895691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895691	2023-12-30T14:22:10 Z	Unforgettablepl	Snake Escaping (JOI18_snake_escaping)	C++17	12 / 100	2000 ms	64648 KB

snake_escaping

//#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-