oj.uz

Submission #381173

# Submission time Handle Problem Language Result Execution time Memory
381173 2021-03-24T16:54:55 Z VodkaInTheJar parentrises (BOI18_parentrises) C++14
72 / 100
 575 ms 11772 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 = 303;

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 481 ms 1112 KB Output is correct
2 Correct 499 ms 1112 KB Output is correct
3 Correct 483 ms 1112 KB Output is correct
4 Correct 488 ms 1004 KB Output is correct
5 Correct 489 ms 1004 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 1112 KB Output is correct
2 Correct 479 ms 1004 KB Output is correct
3 Correct 493 ms 1112 KB Output is correct
4 Correct 481 ms 1112 KB Output is correct
5 Correct 503 ms 1112 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 1112 KB Output is correct
2 Correct 479 ms 1004 KB Output is correct
3 Correct 493 ms 1112 KB Output is correct
4 Correct 481 ms 1112 KB Output is correct
5 Correct 503 ms 1112 KB Output is correct
6 Correct 499 ms 1112 KB Output is correct
7 Correct 487 ms 1112 KB Output is correct
8 Correct 504 ms 1112 KB Output is correct
9 Correct 477 ms 1112 KB Output is correct
10 Correct 499 ms 1132 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 1112 KB Output is correct
2 Correct 479 ms 1004 KB Output is correct
3 Correct 493 ms 1112 KB Output is correct
4 Correct 481 ms 1112 KB Output is correct
5 Correct 503 ms 1112 KB Output is correct
6 Correct 499 ms 1112 KB Output is correct
7 Correct 487 ms 1112 KB Output is correct
8 Correct 504 ms 1112 KB Output is correct
9 Correct 477 ms 1112 KB Output is correct
10 Correct 499 ms 1132 KB Output is correct
11 Correct 477 ms 1116 KB Output is correct
12 Correct 504 ms 1244 KB Output is correct
13 Correct 482 ms 1132 KB Output is correct
14 Correct 501 ms 1116 KB Output is correct
15 Correct 500 ms 1260 KB Output is correct
16 Correct 477 ms 1132 KB Output is correct
17 Correct 484 ms 2344 KB Output is correct
18 Correct 477 ms 1360 KB Output is correct
19 Correct 479 ms 1772 KB Output is correct
20 Correct 491 ms 2328 KB Output is correct
21 Correct 575 ms 1772 KB Output is correct
22 Correct 537 ms 11756 KB Output is correct
23 Correct 559 ms 3192 KB Output is correct
24 Correct 526 ms 6820 KB Output is correct
25 Correct 539 ms 11772 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 1176 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 1176 KB Output is correct
2 Correct 494 ms 1112 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 1176 KB Output is correct
2 Correct 494 ms 1112 KB Output is correct
3 Incorrect 495 ms 1004 KB Output isn't correct