oj.uz

Submission #828097

# Submission time Handle Problem Language Result Execution time Memory
828097 2023-08-17T04:29:04 Z NhanBeoo Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 1940 ms 65536 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")

#include <bits/stdc++.h>
using namespace std;

// #define int ll
#define MAX LLONG_MAX
#define st first
#define nd second
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;

struct Trie{
	struct Node{
		int cnt, exist, sum;
		Node* child[2];
		Node(){
			cnt = exist = sum = 0;
			child[0] = child[1] = NULL;
		}
	};
	Node* root;
	Trie(){
		root = new Node();
	}
	int LG;
	void init(int n){
		LG = n-1;
	}
	void add(int n, int val){
		Node* p = root;
		for(int i=LG; i>=0; i--){
			bool c = n & (1<<i);
			if(p->child[c] == NULL) p->child[c] = new Node();
			p = p->child[c];
			p->cnt++;
		}
		p->exist++;
		p->sum += val;
	}
	int dequy(Node* p, string& s, int i){
		if(i == LG + 1) return p->sum;
		if(s[i] == '0') return dequy(p->child[0], s, i+1);
		else if(s[i] == '1') return dequy(p->child[1], s, i+1);
		else return dequy(p->child[0], s, i+1) + dequy(p->child[1], s, i+1);
	}
	int find(string s){
		return dequy(root, s, 0);
	}
} trie;

map<string, int> m;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, q; cin >> n >> q;
	string s; cin >> s;
	trie.init(n);
	for(int i=0; i<(1<<n); i++) trie.add(i, s[i] - '0');
	while(q--){
		string tmp; cin >> tmp;
		if(m[tmp] != 0) cout << m[tmp] << endl;
		else{
			int ans = trie.find(tmp);
			m[tmp] = ans;
			cout << ans << endl;
		}
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 259 ms 15196 KB Output is correct
12 Correct 374 ms 14872 KB Output is correct
13 Correct 456 ms 14776 KB Output is correct
14 Correct 406 ms 14500 KB Output is correct
15 Correct 412 ms 15356 KB Output is correct
16 Correct 498 ms 15552 KB Output is correct
17 Correct 592 ms 18896 KB Output is correct
18 Correct 148 ms 16076 KB Output is correct
19 Correct 253 ms 13156 KB Output is correct
20 Correct 352 ms 14892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 259 ms 15196 KB Output is correct
12 Correct 374 ms 14872 KB Output is correct
13 Correct 456 ms 14776 KB Output is correct
14 Correct 406 ms 14500 KB Output is correct
15 Correct 412 ms 15356 KB Output is correct
16 Correct 498 ms 15552 KB Output is correct
17 Correct 592 ms 18896 KB Output is correct
18 Correct 148 ms 16076 KB Output is correct
19 Correct 253 ms 13156 KB Output is correct
20 Correct 352 ms 14892 KB Output is correct
21 Correct 379 ms 18868 KB Output is correct
22 Correct 492 ms 19524 KB Output is correct
23 Correct 921 ms 34996 KB Output is correct
24 Correct 673 ms 24868 KB Output is correct
25 Correct 667 ms 22936 KB Output is correct
26 Correct 1246 ms 45044 KB Output is correct
27 Correct 1900 ms 65536 KB Output is correct
28 Correct 155 ms 20796 KB Output is correct
29 Correct 388 ms 16928 KB Output is correct
30 Correct 486 ms 19548 KB Output is correct
31 Correct 1108 ms 35748 KB Output is correct
32 Correct 682 ms 25776 KB Output is correct
33 Correct 600 ms 20824 KB Output is correct
34 Correct 1141 ms 44636 KB Output is correct
35 Correct 1940 ms 65536 KB Output is correct
36 Correct 144 ms 16720 KB Output is correct
37 Correct 382 ms 18860 KB Output is correct
38 Correct 499 ms 17424 KB Output is correct
39 Correct 877 ms 35008 KB Output is correct
40 Correct 653 ms 24784 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Runtime error 73 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 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 259 ms 15196 KB Output is correct
12 Correct 374 ms 14872 KB Output is correct
13 Correct 456 ms 14776 KB Output is correct
14 Correct 406 ms 14500 KB Output is correct
15 Correct 412 ms 15356 KB Output is correct
16 Correct 498 ms 15552 KB Output is correct
17 Correct 592 ms 18896 KB Output is correct
18 Correct 148 ms 16076 KB Output is correct
19 Correct 253 ms 13156 KB Output is correct
20 Correct 352 ms 14892 KB Output is correct
21 Correct 379 ms 18868 KB Output is correct
22 Correct 492 ms 19524 KB Output is correct
23 Correct 921 ms 34996 KB Output is correct
24 Correct 673 ms 24868 KB Output is correct
25 Correct 667 ms 22936 KB Output is correct
26 Correct 1246 ms 45044 KB Output is correct
27 Correct 1900 ms 65536 KB Output is correct
28 Correct 155 ms 20796 KB Output is correct
29 Correct 388 ms 16928 KB Output is correct
30 Correct 486 ms 19548 KB Output is correct
31 Correct 1108 ms 35748 KB Output is correct
32 Correct 682 ms 25776 KB Output is correct
33 Correct 600 ms 20824 KB Output is correct
34 Correct 1141 ms 44636 KB Output is correct
35 Correct 1940 ms 65536 KB Output is correct
36 Correct 144 ms 16720 KB Output is correct
37 Correct 382 ms 18860 KB Output is correct
38 Correct 499 ms 17424 KB Output is correct
39 Correct 877 ms 35008 KB Output is correct
40 Correct 653 ms 24784 KB Output is correct
41 Runtime error 73 ms 65536 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -