oj.uz

Submission #709275

# Submission time Handle Problem Language Result Execution time Memory
709275 2023-03-13T10:06:20 Z vjudge1 Homework (CEOI22_homework) C++17
0 / 100
 45 ms 22528 KB 
#include<bits/stdc++.h>

#define x first
#define y second
#define sz(v) (int)v.size()
#define pb push_back
#define nl "\n"

using namespace std;

const int N = (int)1e6 + 7;
const int inf = (int)1e9 + 7;
     
int n, pos[N], p[N], e[N];
bool dp[300][16][1 << 16];
string s;

void calc(int v, int l, int r) {
	if(l == r) {
		for(int i = 0; i < n; ++i) {
			dp[v][i][1 << i] = 1;
		}
		return;
	}		
	bool tp = (s[l + 1] == 'a');                 
	int mid = e[l];
	calc(v * 2, l + 4, mid - 1);
	calc(v * 2 + 1, mid + 1, r - 1);
	for(int mask = 0; mask < (1 << n); ++mask) {
		int msk = (((1 << n) - 1) ^ mask);
		for(int s = msk; s; s = (s - 1) & msk) {
			for(int x = 0; x < n; ++x) {
				for(int y = 0; y < n; ++y) {
					dp[v][(tp ? max(x, y) : min(x, y))][mask | s] |= (dp[v * 2][x][mask] & dp[v * 2 + 1][y][s]);		
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cin >> s;
	for(int i = 0; i < sz(s); ++i) {
		if(s[i] == '?') {
			pos[i] = ++n;
		}
	}
	stack<int> st;
	for(int i = 0; i < sz(s); ++i) {
		if(s[i] == 'm') st.push(i);		
		if(s[i] == ',') {
			assert(!st.empty());
			e[st.top()] = i;
			st.pop();
		}
	}
	calc(1, 0, sz(s) - 1);
	int ans = 0;
	for(int i = 0; i < n; ++i) ans += dp[1][i][(1 << n) - 1];
	cout << ans;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 976 KB Output is correct
2 Correct 39 ms 920 KB Output is correct
3 Correct 41 ms 932 KB Output is correct
4 Correct 39 ms 980 KB Output is correct
5 Correct 40 ms 984 KB Output is correct
6 Correct 38 ms 872 KB Output is correct
7 Correct 42 ms 920 KB Output is correct
8 Correct 35 ms 860 KB Output is correct
9 Correct 39 ms 944 KB Output is correct
10 Correct 40 ms 944 KB Output is correct
11 Correct 40 ms 988 KB Output is correct
12 Correct 45 ms 900 KB Output is correct
13 Correct 38 ms 1004 KB Output is correct
14 Correct 39 ms 984 KB Output is correct
15 Correct 37 ms 984 KB Output is correct
16 Runtime error 6 ms 744 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 976 KB Output is correct
2 Correct 39 ms 920 KB Output is correct
3 Correct 41 ms 932 KB Output is correct
4 Correct 39 ms 980 KB Output is correct
5 Correct 40 ms 984 KB Output is correct
6 Correct 38 ms 872 KB Output is correct
7 Correct 42 ms 920 KB Output is correct
8 Correct 35 ms 860 KB Output is correct
9 Correct 39 ms 944 KB Output is correct
10 Correct 40 ms 944 KB Output is correct
11 Correct 40 ms 988 KB Output is correct
12 Correct 45 ms 900 KB Output is correct
13 Correct 38 ms 1004 KB Output is correct
14 Correct 39 ms 984 KB Output is correct
15 Correct 37 ms 984 KB Output is correct
16 Runtime error 6 ms 744 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 22528 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 976 KB Output is correct
2 Correct 39 ms 920 KB Output is correct
3 Correct 41 ms 932 KB Output is correct
4 Correct 39 ms 980 KB Output is correct
5 Correct 40 ms 984 KB Output is correct
6 Correct 38 ms 872 KB Output is correct
7 Correct 42 ms 920 KB Output is correct
8 Correct 35 ms 860 KB Output is correct
9 Correct 39 ms 944 KB Output is correct
10 Correct 40 ms 944 KB Output is correct
11 Correct 40 ms 988 KB Output is correct
12 Correct 45 ms 900 KB Output is correct
13 Correct 38 ms 1004 KB Output is correct
14 Correct 39 ms 984 KB Output is correct
15 Correct 37 ms 984 KB Output is correct
16 Runtime error 6 ms 744 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 976 KB Output is correct
2 Correct 39 ms 920 KB Output is correct
3 Correct 41 ms 932 KB Output is correct
4 Correct 39 ms 980 KB Output is correct
5 Correct 40 ms 984 KB Output is correct
6 Correct 38 ms 872 KB Output is correct
7 Correct 42 ms 920 KB Output is correct
8 Correct 35 ms 860 KB Output is correct
9 Correct 39 ms 944 KB Output is correct
10 Correct 40 ms 944 KB Output is correct
11 Correct 40 ms 988 KB Output is correct
12 Correct 45 ms 900 KB Output is correct
13 Correct 38 ms 1004 KB Output is correct
14 Correct 39 ms 984 KB Output is correct
15 Correct 37 ms 984 KB Output is correct
16 Runtime error 6 ms 744 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -