Submission #381175

#	Time	Username	Problem	Language	Result	Execution time	Memory
381175		VodkaInTheJar	parentrises (BOI18_parentrises)	C++14	100 / 100	569 ms	11856 KiB

parentrises

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int mod = 1e9 + 7;

int add(int a, int b)
{
	a += b;
	if (a >= mod)
	a -= mod;
	
	return a;
}

int p, t;
void read()
{
	cin >> p >> t;
}

const int maxn = 307;

int dp[maxn][maxn * 2];
int ans[maxn];
void solve()
{
	for (int i = -1200; i <= 600; i++)
	{
		//if (3 * i > j || i < -j || i > j)
		//continue;
		
		memset(dp, 0, sizeof(dp));
		
		dp[0][300] = 1;
		for (int p = 1; p <= 300; p++)
		for (int k = 0; k <= 600; k++)
		{
			int k1 = k - 300;
			if (3 * k1 < -p || i > 3 * k1 - p)
			continue;
			
			dp[p][k] = add(dp[p-1][k-1], dp[p-1][k+1]);
		}
		  
		for (int j = 1; j <= 300; j++)
		{
			int other = i + j;
			if (other % 3 != 0)
			continue;
			
			other /= 3; 
			if (3 * other > j || other < -j || other > j)
			continue;
			
			ans[j] = add(ans[j], dp[j][other+300]);
		}
	}
	
	while (t--)
	{
		if (p == 1)
		{
			string s;
			cin >> s; 
			
			int n = (int)s.size();
			vector <int> color(n, 0);
			
			stack <int> st;
			for (int i = 0; i < n; i++)
			{
				if (s[i] == '(')
				st.push(i);
				
				else 
				{
					if (!st.empty())
					{
						color[st.top()] += 1; 
						color[i] += 1; 
						
						st.pop();
					}
				}
			}
			
			while (!st.empty())
			st.pop();
			
			vector <int> to_add, to_sub;
		    for (int i = 0; i < n; i++)
		    if (color[i])
		    {
				if (s[i] == '(')
				to_add.push_back(i);
				
				
				else 
				to_sub.push_back(i);
			}
			
			reverse(to_sub.begin(), to_sub.end());
			
			int balance = 0, min_bb = 0;
			for (int i = 0; i < n; i++)
			if (!color[i])
			{
				if (s[i] == '(')
				balance++;
				
				else 
				balance--;
				
				min_bb = min(min_bb, balance);
			}
			
			bool can = false; 
			for (int i = -min_bb; i <= min((int)to_add.size(), -min_bb); i++)
			{
				int curr_balance = balance + i;
				if (curr_balance < 0)
				continue;
				
				if (curr_balance > (int)to_sub.size())
				continue;
				
			    vector <bool> is(n, false);
			    for (int j = 0; j < i; j++)
			    is[to_add[j]] = true; 
			    
			    for (int j = 0; j < curr_balance; j++)
			    is[to_sub[j]] = true; 
			    
			    int bb = 0;
			    bool curr_can = true;
			    for (int j = 0; j < n; j++)
			    {
					if (!color[j] || is[j])
					{
						if (s[j] == '(')
						bb++;
						
						else 
						bb--;
					}
					
					if (bb < 0)
					{
						curr_can = false;
						break;
					}
				}
				
				if (curr_can)
				{ 
					for (int j = 0; j < n; j++)
					if (!color[j] || is[j])
					color[j] += 2; 
					
					can = true;
					break;
				}
			}
			
			if (!can)
			cout << "impossible" << endl;
			
			else 
			{
				for (int i = 0; i < n; i++)
				{
					if (color[i] == 3)
					cout << "G";
					
					else
					if (color[i] == 1)
					cout << "B";
					
					else 
					cout << "R"; 
				}
				
				cout << endl; 
			}
 		}
 		
 		else 
 		{
			int n;
			cin >> n;
			cout << ans[n] << endl; 
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	read();
	solve();
}

• 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