oj.uz

Submission #63549

# Submission time Handle Problem Language Result Execution time Memory
63549 2018-08-02T06:23:26 Z Bruteforceman parentrises (BOI18_parentrises) C++11
100 / 100
 337 ms 219168 KB 
#include "bits/stdc++.h"
using namespace std;
// vector <char> v[1000010];

string solve(string s) {
	int n = s.size();
	stack <int> p;
	stack <int> q;
	string ans;
	for(int i = 0; i < n; i++) ans += '#';
	for(int i = 0; i < n; i++) {
		if(s[i] == ')') {
			if(p.empty()) {
				if(q.empty()) return "impossible";
				else {
					ans[q.top()] = 'G';
					ans[i] = 'B';
					q.pop();
				}
			} else {
				ans[p.top()] = 'R';
				ans[i] = 'R';
				p.pop();
			}
		} else {
			p.push(i);
			q.push(i);
		}
	}
	stack <int> thic;
	for(int i = 0; i < n; i++) {
		if(ans[i] == '#') {
			thic.push(i);
		} else if (s[i] == ')' && !thic.empty()) {
			ans[thic.top()] = 'B';
			ans[i] = 'G';
			thic.pop();
		}
	}
	if(thic.empty()) return ans;
	else return "impossible";
}
const int mod = 1000000000 + 7;
int mem[301][301][301];
int fem[301][301][301];
int dp(int cur, int p, int q) {
	if(cur == 0) {
		return p == 0;
	}
	if(mem[cur][p][q] != -1) return mem[cur][p][q];
	int ans = 0;
	ans += dp(cur - 1, p + 1, q + 1);
	if(p > 0) ans += dp(cur - 1, p - 1, q);
	else if(q > 0) ans += dp(cur - 1, p, q - 1);
	ans %= mod;
	return mem[cur][p][q] = ans;
}
int fn(int cur, int p, int q) {
	if(cur == 0) {
		return q == 0;
	}
	if(fem[cur][p][q] != -1) return fem[cur][p][q];
	int ans = 0;
	ans += fn(cur - 1, p + 1, q + 1);
	if(p > 1) {
		ans += fn(cur - 1, p - 1, max(0, q - 2));
	}
	ans %= mod;
	return fem[cur][p][q] = ans;
}

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie(0);
	int p;
	cin >> p;
	int t;
	cin >> t;
	memset(mem, -1, sizeof mem);
	memset(fem, -1, sizeof fem);
	while(t--) {
		if(p == 1) {
			string s;
			cin >> s;
			cout << solve(s) << '\n';
		} else {
			int n;
			cin >> n;
			long long ans = 0;
			for(int i = 0; i <= n; i++) {
				ans += 1LL * dp(i, 0, 0) * fn(n-i, 0, 0);
				ans %= mod;
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 213752 KB Output is correct
2 Correct 196 ms 214104 KB Output is correct
3 Correct 197 ms 214104 KB Output is correct
4 Correct 193 ms 214104 KB Output is correct
5 Correct 198 ms 214104 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 214104 KB Output is correct
2 Correct 200 ms 214104 KB Output is correct
3 Correct 201 ms 214104 KB Output is correct
4 Correct 202 ms 214104 KB Output is correct
5 Correct 201 ms 214108 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 214104 KB Output is correct
2 Correct 200 ms 214104 KB Output is correct
3 Correct 201 ms 214104 KB Output is correct
4 Correct 202 ms 214104 KB Output is correct
5 Correct 201 ms 214108 KB Output is correct
6 Correct 205 ms 214108 KB Output is correct
7 Correct 200 ms 214108 KB Output is correct
8 Correct 204 ms 214108 KB Output is correct
9 Correct 209 ms 214108 KB Output is correct
10 Correct 202 ms 214124 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 214104 KB Output is correct
2 Correct 200 ms 214104 KB Output is correct
3 Correct 201 ms 214104 KB Output is correct
4 Correct 202 ms 214104 KB Output is correct
5 Correct 201 ms 214108 KB Output is correct
6 Correct 205 ms 214108 KB Output is correct
7 Correct 200 ms 214108 KB Output is correct
8 Correct 204 ms 214108 KB Output is correct
9 Correct 209 ms 214108 KB Output is correct
10 Correct 202 ms 214124 KB Output is correct
11 Correct 207 ms 214124 KB Output is correct
12 Correct 201 ms 214124 KB Output is correct
13 Correct 199 ms 214124 KB Output is correct
14 Correct 195 ms 214156 KB Output is correct
15 Correct 199 ms 214172 KB Output is correct
16 Correct 201 ms 214192 KB Output is correct
17 Correct 205 ms 214704 KB Output is correct
18 Correct 182 ms 214704 KB Output is correct
19 Correct 183 ms 214704 KB Output is correct
20 Correct 167 ms 214908 KB Output is correct
21 Correct 202 ms 214908 KB Output is correct
22 Correct 199 ms 219168 KB Output is correct
23 Correct 224 ms 219168 KB Output is correct
24 Correct 232 ms 219168 KB Output is correct
25 Correct 217 ms 219168 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 219168 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 219168 KB Output is correct
2 Correct 184 ms 219168 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 219168 KB Output is correct
2 Correct 184 ms 219168 KB Output is correct
3 Correct 337 ms 219168 KB Output is correct