oj.uz

Submission #828098

# Submission time Handle Problem Language Result Execution time Memory
828098 2023-08-17T04:30:48 Z NhanBeoo Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 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 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 452 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 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 244 ms 4640 KB Output is correct
12 Correct 389 ms 4428 KB Output is correct
13 Correct 442 ms 4120 KB Output is correct
14 Correct 394 ms 3900 KB Output is correct
15 Correct 401 ms 4924 KB Output is correct
16 Correct 484 ms 5196 KB Output is correct
17 Correct 576 ms 8656 KB Output is correct
18 Correct 144 ms 5684 KB Output is correct
19 Correct 245 ms 2668 KB Output is correct
20 Correct 336 ms 4408 KB Output is correct

Subtask #3
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 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 244 ms 4640 KB Output is correct
12 Correct 389 ms 4428 KB Output is correct
13 Correct 442 ms 4120 KB Output is correct
14 Correct 394 ms 3900 KB Output is correct
15 Correct 401 ms 4924 KB Output is correct
16 Correct 484 ms 5196 KB Output is correct
17 Correct 576 ms 8656 KB Output is correct
18 Correct 144 ms 5684 KB Output is correct
19 Correct 245 ms 2668 KB Output is correct
20 Correct 336 ms 4408 KB Output is correct
21 Correct 374 ms 5496 KB Output is correct
22 Correct 468 ms 6132 KB Output is correct
23 Correct 991 ms 21500 KB Output is correct
24 Correct 691 ms 11348 KB Output is correct
25 Correct 663 ms 9572 KB Output is correct
26 Correct 1338 ms 31552 KB Output is correct
27 Execution timed out 2035 ms 65536 KB Time limit exceeded
28 Halted 0 ms 0 KB -

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 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Runtime error 72 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 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 244 ms 4640 KB Output is correct
12 Correct 389 ms 4428 KB Output is correct
13 Correct 442 ms 4120 KB Output is correct
14 Correct 394 ms 3900 KB Output is correct
15 Correct 401 ms 4924 KB Output is correct
16 Correct 484 ms 5196 KB Output is correct
17 Correct 576 ms 8656 KB Output is correct
18 Correct 144 ms 5684 KB Output is correct
19 Correct 245 ms 2668 KB Output is correct
20 Correct 336 ms 4408 KB Output is correct
21 Correct 374 ms 5496 KB Output is correct
22 Correct 468 ms 6132 KB Output is correct
23 Correct 991 ms 21500 KB Output is correct
24 Correct 691 ms 11348 KB Output is correct
25 Correct 663 ms 9572 KB Output is correct
26 Correct 1338 ms 31552 KB Output is correct
27 Execution timed out 2035 ms 65536 KB Time limit exceeded
28 Halted 0 ms 0 KB -