Submission #255167

#	Time	Username	Problem	Language	Result	Execution time	Memory
255167		amoo_safar	parentrises (BOI18_parentrises)	C++14	100 / 100	59 ms	14352 KiB

parentrises

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 3e2 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

str Solve1(){
	vector<int> O, C;
	int sm = 0;
	str s;
	cin >> s;
	int n = s.size();
	vector<int> mk(n, 0);

	for(int i = 0; i < n; i++){
		if(s[i] == '('){
			O.pb(i);
			sm ++;
		} else {
			C.pb(i);
			sm --;
		}
	}
	reverse(all(C));

	str Im = "impossible";
	int Ao = (sm <= 0 ? -sm: 0);
	int Ac = (sm >= 0 ? sm: 0);

	int idx = -1;
	for(int i = 0; i < n; i++){
		if(Ao + i > (int)O.size()) break;
		if(Ac + i > (int)C.size()) break;
		int po = (Ao + i == 0 ? -1 : O[Ao + i - 1]);
		int pc = (Ac + i == 0 ? n : C[Ac + i - 1]);
		if(po >= pc) break;
		idx = i;
	}
	//debug(idx);
	if(idx == -1) return Im;
	for(int i = 0; i < Ao + idx; i++) mk[O[i]] = 1;
	for(int i = 0; i < Ac + idx; i++) mk[C[i]] = 1;

	str res = "";
	int Sr = 0, Sb = 0;
	for(int i = 0; i < n; i++){
		if(mk[i]){
			res += "G";
			if(s[i] == '('){
				Sr ++;
				Sb ++;
			} else {
				Sr --;
				Sb --;
			}
		} else {
			if(s[i] == '('){
				if(Sr < Sb) Sr ++, res += "R";
				else Sb ++, res += "B";
			} else {
				if(Sr > Sb) Sr --, res += "R";
				else Sb --, res += "B";
			}
		}
		if(min(Sr, Sb) < 0) return Im;
	}

	assert(Sr == 0); assert(Sb == 0);
	return res;
}

ll dp[N][N][3];

ll ans[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	dp[1][2][0] = 1;
	dp[1][1][1] = 1;
	
	for(int i = 1; i + 1 < N; i++){
		for(int sm = 0; sm < N; sm ++){
			dp[i][sm][0] %= Mod;
			dp[i][sm][1] %= Mod;
			dp[i][sm][2] %= Mod;

			if(dp[i][sm][0]){
				if(sm + 1 < N) dp[i + 1][sm + 1][1] += dp[i][sm][0];
				if(sm + 2 < N) dp[i + 1][sm + 2][0] += dp[i][sm][0];
				
				if(sm >= 1) dp[i + 1][sm - 1][0] += dp[i][sm][0];
				if(sm >= 2) dp[i + 1][sm - 2][2] += dp[i][sm][0];
			}
			
			if(dp[i][sm][1]){
				
				if(sm + 1 < N) dp[i + 1][sm + 1][1] += dp[i][sm][1];
				//dp[i + 1][sm + 2][0] += dp[i][sm][0];
				
				//if(sm >= 1) dp[i + 1][sm - 1][0] += dp[i][sm][0];
				if(sm >= 2) dp[i + 1][sm - 2][2] += dp[i][sm][1];
			}
			
			if(dp[i][sm][2]){
				if(sm + 1 < N) dp[i + 1][sm + 1][2] += dp[i][sm][2];
				//dp[i + 1][sm + 2][0] += dp[i][sm][2];
				
				//if(sm >= 1) dp[i + 1][sm - 1][0] += dp[i][sm][2];
				if(sm >= 2) dp[i + 1][sm - 2][2] += dp[i][sm][2];
			}
		}
		
		ans[i] = (dp[i][0][0] + dp[i][0][1] + dp[i][0][2]) % Mod;
	}


	int PR;
	cin >> PR;
	int T;
	cin >> T;
	while(T --){
		if(PR == 1) cout << Solve1() << '\n';
		else {
			int m;
			cin >> m;
			cout << ans[m] << '\n';
		}
	}
	return 0;
}

• 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