oj.uz

Submission #365430

# Submission time Handle Problem Language Result Execution time Memory
365430 2021-02-11T16:34:49 Z tfg parentrises (BOI18_parentrises) C++17
100 / 100
 91 ms 110700 KB 
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

bool good(const std::string &str) {
	int bal = 0;
	for(auto ch : str) {
		bal += ch == '(' ? 1 : -1;
		if(bal < 0) return false;
	}
	return bal == 0;
}

void solve1() {
	int t;
	std::cin >> t;
	while(t--) {
		std::string str;
		std::cin >> str;
		int n = (int) str.size();
		std::vector<int> pos[2];
		std::vector<int> col(n, 3);
		int bst = 0, sum = 0;
		for(int i = 0; i < n; i++) {
			pos[str[i] == '('].push_back(i);
			sum += str[i] == '(' ? 1 : -1;
			bst = std::min(bst, sum);
		}
		int bal = (int) pos[1].size() - (int) pos[0].size();
		if(bst < 0) {
			bal -= bst;
			bst = -bst;
			for(int i = 0; i < 2*bst && i < (int) pos[0].size(); i++) {
				col[pos[0][i]] = i % 2 == 0 ? 1 : 2;
			}
		}
		if(bal > 0) {
			for(int i = 0; i < 2*bal && i < (int) pos[1].size(); i++) {
				col[pos[1][(int) pos[1].size() - i - 1]] = i % 2 == 0 ? 1 : 2;
			}
		}
		
		std::string haha[2];
		for(int i = 0; i < n; i++) {
			if(col[i] & 1) haha[0] += str[i];
			if(col[i] & 2) haha[1] += str[i];
		}
		if(good(haha[0]) && good(haha[1])) {
			for(int i = 0; i < n; i++) {
				char ch;
				if(col[i] == 3) {
					ch = 'G';
				} else if(col[i] == 1) {
					ch = 'R';
				} else {
					ch = 'B';
				}
				std::cout << ch;
			}
			std::cout << '\n';
		} else {
			std::cout << "impossible\n";
		}
	}
}

const int ms = 303;
const int MOD = 1e9 + 7;
long long dp[ms][ms][ms];
long long catalan[ms];
long long wtf[ms];

void solve2() {
	int t;
	std::cin >> t;
	catalan[0] = 1;
	for(int i = 2; i < ms; i += 2) {
		for(int j = 0; j < i; j += 2) {
			catalan[i] = (catalan[i] + catalan[j] * catalan[i-j-2]) % MOD;
		}
	}
	dp[0][0][0] = 1;
	for(int i = 0; i+1 < ms; i++) {
		for(int sum = 0; sum <= i; sum++) {
			for(int mx = 0; mx <= i; mx++) {
				dp[i][sum][mx] %= MOD;
				dp[i+1][sum+1][mx] += dp[i][sum][mx];
				if(sum > 0) {
					dp[i+1][sum-1][mx+1] += dp[i][sum][mx];
				} else if(mx > 0) {
					wtf[i+1] = (dp[i][sum][mx] + wtf[i+1]) % MOD;
					dp[i+1][sum][mx-1] += dp[i][sum][mx];
				}
			}
		}
	}
	wtf[0] = 1;
	while(t--) {
		int n;
		std::cin >> n;
		long long ans = 0;
		for(int i = 0; i <= n; i++) {
			for(int j = 0; i+j <= n; j += 2) {
				ans = (ans + wtf[i] * catalan[j] % MOD * wtf[n-i-j]) % MOD;
			}
		}
		std::cout << ans << '\n';
	}
}

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int P;
	std::cin >> P;
	if(P == 1) {
		solve1();
	} else {
		solve2();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 8 ms 620 KB Output is correct
17 Correct 8 ms 1860 KB Output is correct
18 Correct 7 ms 712 KB Output is correct
19 Correct 8 ms 1260 KB Output is correct
20 Correct 8 ms 1768 KB Output is correct
21 Correct 61 ms 2028 KB Output is correct
22 Correct 77 ms 15376 KB Output is correct
23 Correct 67 ms 3300 KB Output is correct
24 Correct 68 ms 7800 KB Output is correct
25 Correct 74 ms 15228 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 110700 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 110700 KB Output is correct
2 Correct 79 ms 110620 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 110700 KB Output is correct
2 Correct 79 ms 110620 KB Output is correct
3 Correct 91 ms 110700 KB Output is correct