oj.uz

Submission #828102

# Submission time Handle Problem Language Result Execution time Memory
828102 2023-08-17T04:37:04 Z NhanBeoo Snake Escaping (JOI18_snake_escaping) C++17
5 / 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 sum;
		Node* child[2];
		Node(){
			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->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;

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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 357 ms 4264 KB Output is correct
12 Correct 511 ms 4048 KB Output is correct
13 Correct 317 ms 3188 KB Output is correct
14 Correct 327 ms 3272 KB Output is correct
15 Correct 703 ms 4388 KB Output is correct
16 Correct 471 ms 3560 KB Output is correct
17 Correct 433 ms 3472 KB Output is correct
18 Execution timed out 2072 ms 5108 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 357 ms 4264 KB Output is correct
12 Correct 511 ms 4048 KB Output is correct
13 Correct 317 ms 3188 KB Output is correct
14 Correct 327 ms 3272 KB Output is correct
15 Correct 703 ms 4388 KB Output is correct
16 Correct 471 ms 3560 KB Output is correct
17 Correct 433 ms 3472 KB Output is correct
18 Execution timed out 2072 ms 5108 KB Time limit exceeded
19 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Runtime error 85 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 357 ms 4264 KB Output is correct
12 Correct 511 ms 4048 KB Output is correct
13 Correct 317 ms 3188 KB Output is correct
14 Correct 327 ms 3272 KB Output is correct
15 Correct 703 ms 4388 KB Output is correct
16 Correct 471 ms 3560 KB Output is correct
17 Correct 433 ms 3472 KB Output is correct
18 Execution timed out 2072 ms 5108 KB Time limit exceeded
19 Halted 0 ms 0 KB -