Submission #65176

#	Time	Username	Problem	Language	Result	Execution time	Memory
65176		spencercompton	parentrises (BOI18_parentrises)	C++14	100 / 100	778 ms	11408 KiB

parentrises

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007LL;
ll dp[2][403][403];
ll cur;
ll f(int lbal, int rbal){
	if(lbal<0){
		return 0LL;
	}
	lbal = min(lbal,201);
	lbal = max(lbal,-201);
	rbal = min(rbal,201);
	rbal = max(rbal,-201);
	return dp[1-cur][lbal+201][rbal+201];
}
ll go(int rem, int lbal, int rbal){
	if(lbal<0){
		return 0LL;
	}
	if(rem==0){
		ll ret = 1LL;
		if(lbal<0 || rbal<0){
			return 0LL;
		}
		dp[cur][lbal+201][rbal+201] = ret;
		return ret;
	}
	ll ret = 0LL;
	//(
	ret += f(lbal+2,min(rbal-1,-1));
	ll a = f(lbal+2,min(rbal-1,-1));
	//)
	ret += f(lbal-1,rbal+2);
	ll b = f(lbal-1,rbal+2);
	ret %= mod;
	dp[cur][lbal+201][rbal+201] = ret;
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int p, cases;
	cin >> p >> cases;
	if(p==1){
		for(int z = 1; z<=cases; z++){
			string s;
			cin >> s;
			bool pos = true;
			int open = 0;
			int close = 0;
			for(int i = 0; i<s.length(); i++){
				if(s[i]=='('){
					open++;
				}
				else{
					close++;
				}
				if(close>2*open){
					pos = false;
				}
			}
			open = 0;
			close = 0;
			for(int i = s.length()-1; i>=0; i--){
				if(s[i]=='('){
					open++;
				}
				else{
					close++;
				}
				if(open > 2*close){
					pos = false;
				}
			}
			int n = (int)s.length();
			int color[n];
			//G = 0, B = 1, R = 2
			for(int i = 0; i<n; i++){
				color[i] = 0;
			}
			open = 0;
			close = 0;
			vector<int> op;
			vector<int> cl;
			bool ok = true;
			vector<int> op2;
			vector<int> cl2;
			int point = 0;
			for(int i = 0; i<n; i++){
				if(s[i]=='('){
					op.push_back(i);
					open++;
				}
				else{
					cl.push_back(i);
					close++;
					if(close>open){
						if(point+2 > cl.size()){
							ok = false;
							break;
						}
						cl2.push_back(cl[point++]);
						cl2.push_back(cl[point++]);
						close--;
					}
				}
			}
			int dif = open-close;
			if(!ok || 2*dif>open){
				assert(!pos);
				cout << "impossible" << endl;
				continue;
			}
			for(int i = 0; i<2*dif; i++){
				op2.push_back(op.back());
				op.pop_back();
			}
			assert(op2.size()%2==0 && cl2.size()%2==0);
			for(int i = 0; i<op2.size(); i+=2){
				color[op2[i]] = 1;
				color[op2[i+1]] = 2;
			}
			for(int i = 0; i<cl2.size(); i+=2){
				color[cl2[i]] = 1;
				color[cl2[i+1]] = 2;
			}
			int bal1 = 0;
			int bal2 = 0;
			for(int i = 0; i<n; i++){
				if(color[i]==0 || color[i]==1){
					if(s[i]=='('){
						bal1++;
					}
					else{
						bal1--;
					}
				}
				if(color[i]==0 || color[i]==2){
					if(s[i]=='('){
						bal2++;
					}
					else{
						bal2--;
					}
				}
				if(bal1<0 || bal2<0){
					ok = false;
				}
			}
			ok &= bal1==0 && bal2==0;
			if(!ok){
				assert(!pos);
				cout << "impossible" << endl;
				continue;
			}
			assert(ok);
			for(int i = 0; i<n; i++){
				if(color[i]==0){
					cout << "G";
				}
				else if(color[i]==1){
					cout << "B";
				}
				else{
					cout << "R";
				}
			}
			cout << endl;
		}
	}
	else{
		ll ans[301];
		cur = 0;
		for(int i = 0; i<=300; i++){
			cur = 1-cur;
			for(int j = -201; j<=201; j++){
				for(int k = -201; k<=201; k++){
					go(i,j,k);
				}
			}
			ans[i] = go(i,0,0);
		}
		for(int i = 0; i<cases; i++){
			int x;
			cin >> x;
			cout << ans[x] << endl;
		}
	}
}

Compilation message (stderr)

parentrises.cpp: In function 'll go(int, int, int)':
parentrises.cpp:32:5: warning: unused variable 'a' [-Wunused-variable]
  ll a = f(lbal+2,min(rbal-1,-1));
     ^
parentrises.cpp:35:5: warning: unused variable 'b' [-Wunused-variable]
  ll b = f(lbal-1,rbal+2);
     ^
parentrises.cpp: In function 'int main()':
parentrises.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<s.length(); i++){
                   ~^~~~~~~~~~~
parentrises.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(point+2 > cl.size()){
          ~~~~~~~~^~~~~~~~~~~
parentrises.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<op2.size(); i+=2){
                   ~^~~~~~~~~~~
parentrises.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<cl2.size(); i+=2){
                   ~^~~~~~~~~~~

• 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