oj.uz

Submission #381174

# Submission time Handle Problem Language Result Execution time Memory
381174 2021-03-24T16:56:44 Z VodkaInTheJar parentrises (BOI18_parentrises) C++14
72 / 100
 577 ms 11776 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;
			
			if (n <= 100)
			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 494 ms 1132 KB Output is correct
2 Correct 506 ms 1132 KB Output is correct
3 Correct 511 ms 1132 KB Output is correct
4 Correct 485 ms 1132 KB Output is correct
5 Correct 494 ms 1132 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1132 KB Output is correct
2 Correct 478 ms 1132 KB Output is correct
3 Correct 478 ms 1132 KB Output is correct
4 Correct 548 ms 1132 KB Output is correct
5 Correct 548 ms 1132 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1132 KB Output is correct
2 Correct 478 ms 1132 KB Output is correct
3 Correct 478 ms 1132 KB Output is correct
4 Correct 548 ms 1132 KB Output is correct
5 Correct 548 ms 1132 KB Output is correct
6 Correct 497 ms 1132 KB Output is correct
7 Correct 568 ms 1132 KB Output is correct
8 Correct 531 ms 1132 KB Output is correct
9 Correct 488 ms 1152 KB Output is correct
10 Correct 577 ms 1132 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1132 KB Output is correct
2 Correct 478 ms 1132 KB Output is correct
3 Correct 478 ms 1132 KB Output is correct
4 Correct 548 ms 1132 KB Output is correct
5 Correct 548 ms 1132 KB Output is correct
6 Correct 497 ms 1132 KB Output is correct
7 Correct 568 ms 1132 KB Output is correct
8 Correct 531 ms 1132 KB Output is correct
9 Correct 488 ms 1152 KB Output is correct
10 Correct 577 ms 1132 KB Output is correct
11 Correct 491 ms 1136 KB Output is correct
12 Correct 492 ms 1260 KB Output is correct
13 Correct 496 ms 1136 KB Output is correct
14 Correct 504 ms 1136 KB Output is correct
15 Correct 486 ms 1264 KB Output is correct
16 Correct 497 ms 1136 KB Output is correct
17 Correct 530 ms 2348 KB Output is correct
18 Correct 485 ms 1360 KB Output is correct
19 Correct 504 ms 1776 KB Output is correct
20 Correct 481 ms 2348 KB Output is correct
21 Correct 567 ms 1904 KB Output is correct
22 Correct 563 ms 11776 KB Output is correct
23 Correct 549 ms 3328 KB Output is correct
24 Correct 529 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 479 ms 1132 KB Output is correct

Subtask #6
16.0 / 16.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 1132 KB Output is correct
2 Correct 477 ms 1132 KB Output is correct
3 Incorrect 509 ms 1156 KB Output isn't correct