oj.uz

Submission #381175

# Submission time Handle Problem Language Result Execution time Memory
381175 2021-03-24T16:57:28 Z VodkaInTheJar parentrises (BOI18_parentrises) C++14
100 / 100
 569 ms 11856 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 1132 KB Output is correct
2 Correct 492 ms 1132 KB Output is correct
3 Correct 485 ms 1132 KB Output is correct
4 Correct 508 ms 1132 KB Output is correct
5 Correct 484 ms 1132 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 1132 KB Output is correct
2 Correct 523 ms 1132 KB Output is correct
3 Correct 515 ms 1132 KB Output is correct
4 Correct 497 ms 1132 KB Output is correct
5 Correct 546 ms 1280 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 1132 KB Output is correct
2 Correct 523 ms 1132 KB Output is correct
3 Correct 515 ms 1132 KB Output is correct
4 Correct 497 ms 1132 KB Output is correct
5 Correct 546 ms 1280 KB Output is correct
6 Correct 479 ms 1132 KB Output is correct
7 Correct 487 ms 1132 KB Output is correct
8 Correct 556 ms 1132 KB Output is correct
9 Correct 475 ms 1132 KB Output is correct
10 Correct 483 ms 1132 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 1132 KB Output is correct
2 Correct 523 ms 1132 KB Output is correct
3 Correct 515 ms 1132 KB Output is correct
4 Correct 497 ms 1132 KB Output is correct
5 Correct 546 ms 1280 KB Output is correct
6 Correct 479 ms 1132 KB Output is correct
7 Correct 487 ms 1132 KB Output is correct
8 Correct 556 ms 1132 KB Output is correct
9 Correct 475 ms 1132 KB Output is correct
10 Correct 483 ms 1132 KB Output is correct
11 Correct 512 ms 1132 KB Output is correct
12 Correct 485 ms 1264 KB Output is correct
13 Correct 477 ms 1280 KB Output is correct
14 Correct 484 ms 1136 KB Output is correct
15 Correct 490 ms 1264 KB Output is correct
16 Correct 492 ms 1136 KB Output is correct
17 Correct 489 ms 2348 KB Output is correct
18 Correct 486 ms 1364 KB Output is correct
19 Correct 503 ms 1776 KB Output is correct
20 Correct 484 ms 2472 KB Output is correct
21 Correct 543 ms 1904 KB Output is correct
22 Correct 556 ms 11856 KB Output is correct
23 Correct 532 ms 3188 KB Output is correct
24 Correct 553 ms 6824 KB Output is correct
25 Correct 569 ms 11776 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1132 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1132 KB Output is correct
2 Correct 516 ms 1132 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1132 KB Output is correct
2 Correct 516 ms 1132 KB Output is correct
3 Correct 486 ms 1132 KB Output is correct