Submission #61272

#	Time	Username	Problem	Language	Result	Execution time	Memory
61272		Miyukine	parentrises (BOI18_parentrises)	C++14	100 / 100	165 ms	3784 KiB

parentrises

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=(a); i<=(b); ++i)
const int maxn = 1e6 + 5;
typedef pair <int, int> PII;
typedef long long ll;
const int mod = 1e9 + 7;

int dp[2][605][605];
//dp[length][stacksize in RG][stacksize in RB]
int type, n;
string s;
int stos[1000100], DL = 0;
char arr[1000100];
int result[305];

void solveone()
{
	cin >> s;
	int m = (int)s.size();
	DL = 0;
	for (int i = 0; i < m; ++i)
	{
		if (s[i] == '(') stos[++DL] = i, arr[i] = 'R';
		else
		{
			if (DL > 0) 
			{
				arr[stos[DL]] = 'B';
				arr[i] = 'B';
				DL--;
			}
			else arr[i] = 'R';
		}
	}
	
	int wait = 0;
	for (int i = 0; i < m; ++i)
		if (arr[i] == 'R' && s[i] == '(') ++wait;
		else if (arr[i] == 'B' && s[i] == ')' && wait > 0)
		{
			--wait;
			arr[i] = 'G';
		}
	
	if (wait > 0)
	{
		cout << "impossible\n";
		return;
	}
	wait = 0;
	for (int i = m - 1; i >= 0; --i)
	{
		if (arr[i] == 'R' && s[i] == ')') ++wait;
		else if (arr[i] == 'B' && s[i] == '(' && wait > 0)
		{
			--wait;
			arr[i] = 'G';
		}
	}
	if (wait > 0)
	{
		cout << "impossible\n";
		return;
	}
	
	for (int i = 0; i < m; ++i) cout << arr[i];
	cout << "\n";
}

inline void addmod(int &x, int v) { x += v; while (x >= mod) x -= mod; }

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> type;
	if (type == 1)
	{
		cin >> n;
		for (int i=0; i<n; ++i) solveone();
	}
	if (type == 2)
	{
		int tests;
		n = 301;
		dp[0][0][0] = 1; //one sequence
		for (int i=1; i<=n; ++i)
		{
			FOR(j, 0, 604)
				FOR(k, 0, 604) dp[i & 1][j][k] = 0;
			
			FOR(j, 0, i)
				FOR(k, j, 2 * i)
				{
					//i have two options: either update with ) or with (
					if (k) addmod(dp[i & 1][max(j - 2, 0)][k - 1], dp[(i & 1) ^ 1][j][k]);
					addmod(dp[i & 1][j + 1][k + 2], dp[(i & 1) ^ 1][j][k]);
				}
			
			for (int j = 0; j <= 604; ++j) addmod(result[i], dp[i & 1][0][j]);
		}

		cin >> tests;
		while (tests--)
		{
			cin >> n;
			cout << result[n] << "\n";
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28