답안 #709278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
709278	2023-03-13T10:09:51 Z	vjudge1	Homework (CEOI22_homework)	C++17	10 / 100	1000 ms	14428 KB

Main

#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[500][16][1 << 16];
vector<int> ve[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 : ve[mask]) {
				for(int y : ve[s]) {
					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;
		}
	}
	for(int mask = 0; mask < (1 << n); ++mask) {
		for(int i = 0; i < n; ++i) {
			if(mask >> i & 1) ve[mask].pb(i);		
		}
	}
	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
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	2516 KB	Output is correct
2	Correct	9 ms	2484 KB	Output is correct
3	Correct	9 ms	2520 KB	Output is correct
4	Correct	10 ms	2516 KB	Output is correct
5	Correct	10 ms	2456 KB	Output is correct
6	Correct	10 ms	2516 KB	Output is correct
7	Correct	9 ms	2516 KB	Output is correct
8	Correct	10 ms	2496 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	9 ms	2432 KB	Output is correct
11	Correct	10 ms	2516 KB	Output is correct
12	Correct	10 ms	2504 KB	Output is correct
13	Correct	10 ms	2516 KB	Output is correct
14	Correct	9 ms	2448 KB	Output is correct
15	Correct	9 ms	2516 KB	Output is correct
16	Correct	10 ms	2456 KB	Output is correct
17	Correct	10 ms	2544 KB	Output is correct
18	Correct	9 ms	2516 KB	Output is correct
19	Correct	9 ms	2516 KB	Output is correct
20	Correct	10 ms	2516 KB	Output is correct
21	Correct	9 ms	2412 KB	Output is correct
22	Correct	10 ms	2492 KB	Output is correct
23	Correct	10 ms	2516 KB	Output is correct
24	Correct	10 ms	2516 KB	Output is correct
25	Correct	3 ms	2260 KB	Output is correct
26	Correct	4 ms	2260 KB	Output is correct
27	Correct	3 ms	2260 KB	Output is correct
28	Correct	1 ms	1876 KB	Output is correct

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	2516 KB	Output is correct
2	Correct	9 ms	2484 KB	Output is correct
3	Correct	9 ms	2520 KB	Output is correct
4	Correct	10 ms	2516 KB	Output is correct
5	Correct	10 ms	2456 KB	Output is correct
6	Correct	10 ms	2516 KB	Output is correct
7	Correct	9 ms	2516 KB	Output is correct
8	Correct	10 ms	2496 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	9 ms	2432 KB	Output is correct
11	Correct	10 ms	2516 KB	Output is correct
12	Correct	10 ms	2504 KB	Output is correct
13	Correct	10 ms	2516 KB	Output is correct
14	Correct	9 ms	2448 KB	Output is correct
15	Correct	9 ms	2516 KB	Output is correct
16	Correct	10 ms	2456 KB	Output is correct
17	Correct	10 ms	2544 KB	Output is correct
18	Correct	9 ms	2516 KB	Output is correct
19	Correct	9 ms	2516 KB	Output is correct
20	Correct	10 ms	2516 KB	Output is correct
21	Correct	9 ms	2412 KB	Output is correct
22	Correct	10 ms	2492 KB	Output is correct
23	Correct	10 ms	2516 KB	Output is correct
24	Correct	10 ms	2516 KB	Output is correct
25	Correct	3 ms	2260 KB	Output is correct
26	Correct	4 ms	2260 KB	Output is correct
27	Correct	3 ms	2260 KB	Output is correct
28	Correct	1 ms	1876 KB	Output is correct
29	Execution timed out	1078 ms	6912 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	23 ms	14428 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	2516 KB	Output is correct
2	Correct	9 ms	2484 KB	Output is correct
3	Correct	9 ms	2520 KB	Output is correct
4	Correct	10 ms	2516 KB	Output is correct
5	Correct	10 ms	2456 KB	Output is correct
6	Correct	10 ms	2516 KB	Output is correct
7	Correct	9 ms	2516 KB	Output is correct
8	Correct	10 ms	2496 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	9 ms	2432 KB	Output is correct
11	Correct	10 ms	2516 KB	Output is correct
12	Correct	10 ms	2504 KB	Output is correct
13	Correct	10 ms	2516 KB	Output is correct
14	Correct	9 ms	2448 KB	Output is correct
15	Correct	9 ms	2516 KB	Output is correct
16	Correct	10 ms	2456 KB	Output is correct
17	Correct	10 ms	2544 KB	Output is correct
18	Correct	9 ms	2516 KB	Output is correct
19	Correct	9 ms	2516 KB	Output is correct
20	Correct	10 ms	2516 KB	Output is correct
21	Correct	9 ms	2412 KB	Output is correct
22	Correct	10 ms	2492 KB	Output is correct
23	Correct	10 ms	2516 KB	Output is correct
24	Correct	10 ms	2516 KB	Output is correct
25	Correct	3 ms	2260 KB	Output is correct
26	Correct	4 ms	2260 KB	Output is correct
27	Correct	3 ms	2260 KB	Output is correct
28	Correct	1 ms	1876 KB	Output is correct
29	Execution timed out	1078 ms	6912 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	2516 KB	Output is correct
2	Correct	9 ms	2484 KB	Output is correct
3	Correct	9 ms	2520 KB	Output is correct
4	Correct	10 ms	2516 KB	Output is correct
5	Correct	10 ms	2456 KB	Output is correct
6	Correct	10 ms	2516 KB	Output is correct
7	Correct	9 ms	2516 KB	Output is correct
8	Correct	10 ms	2496 KB	Output is correct
9	Correct	9 ms	2528 KB	Output is correct
10	Correct	9 ms	2432 KB	Output is correct
11	Correct	10 ms	2516 KB	Output is correct
12	Correct	10 ms	2504 KB	Output is correct
13	Correct	10 ms	2516 KB	Output is correct
14	Correct	9 ms	2448 KB	Output is correct
15	Correct	9 ms	2516 KB	Output is correct
16	Correct	10 ms	2456 KB	Output is correct
17	Correct	10 ms	2544 KB	Output is correct
18	Correct	9 ms	2516 KB	Output is correct
19	Correct	9 ms	2516 KB	Output is correct
20	Correct	10 ms	2516 KB	Output is correct
21	Correct	9 ms	2412 KB	Output is correct
22	Correct	10 ms	2492 KB	Output is correct
23	Correct	10 ms	2516 KB	Output is correct
24	Correct	10 ms	2516 KB	Output is correct
25	Correct	3 ms	2260 KB	Output is correct
26	Correct	4 ms	2260 KB	Output is correct
27	Correct	3 ms	2260 KB	Output is correct
28	Correct	1 ms	1876 KB	Output is correct
29	Execution timed out	1078 ms	6912 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

답안 #709278

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 13.0

Subtask #3 0 / 13.0

Subtask #4 0 / 30.0

Subtask #5 0 / 34.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 13.0

Subtask #3
0 / 13.0

Subtask #4
0 / 30.0

Subtask #5
0 / 34.0