oj.uz

Submission #828107

# Submission time Handle Problem Language Result Execution time Memory
828107 2023-08-17T05:03:12 Z NhanBeoo Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 4816 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;

int n, q;
string s, tmp;

int dfs(int state, int i){
	// cout << state << ' ' << i << endl;
	if(i == n)  return s[state] - '0';
	if(tmp[i] == '0') return dfs(state, i+1);
	else if(tmp[i] == '1') return dfs(state|(1<<(n-i-1)), i+1);
	else return dfs(state, i+1) + dfs(state|(1<<(n-i-1)), i+1);
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> q >> s;
	while(q--){
		cin >> tmp;
		int state = 0;
		bool ans = false;
		for(int i=0; i<n; i++){
			if(tmp[i] == '0') continue;
			else if(tmp[i] == '1') state |= (1 << (n - i - 1));
			else{
				cout << dfs(state, i) << endl;
				ans = true;
				break;
			}
		}
		if(!ans) cout << (s[state] - '0') << endl;
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 383 ms 4816 KB Output is correct
12 Correct 495 ms 4428 KB Output is correct
13 Correct 301 ms 3644 KB Output is correct
14 Correct 317 ms 3732 KB Output is correct
15 Correct 687 ms 4812 KB Output is correct
16 Correct 408 ms 3904 KB Output is correct
17 Correct 405 ms 3908 KB Output is correct
18 Execution timed out 2065 ms 4320 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 383 ms 4816 KB Output is correct
12 Correct 495 ms 4428 KB Output is correct
13 Correct 301 ms 3644 KB Output is correct
14 Correct 317 ms 3732 KB Output is correct
15 Correct 687 ms 4812 KB Output is correct
16 Correct 408 ms 3904 KB Output is correct
17 Correct 405 ms 3908 KB Output is correct
18 Execution timed out 2065 ms 4320 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 360 ms 3748 KB Output is correct
12 Correct 736 ms 3752 KB Output is correct
13 Correct 60 ms 3748 KB Output is correct
14 Correct 97 ms 3764 KB Output is correct
15 Execution timed out 2070 ms 3856 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 383 ms 4816 KB Output is correct
12 Correct 495 ms 4428 KB Output is correct
13 Correct 301 ms 3644 KB Output is correct
14 Correct 317 ms 3732 KB Output is correct
15 Correct 687 ms 4812 KB Output is correct
16 Correct 408 ms 3904 KB Output is correct
17 Correct 405 ms 3908 KB Output is correct
18 Execution timed out 2065 ms 4320 KB Time limit exceeded
19 Halted 0 ms 0 KB -