Submission #68789

#	Time	Username	Problem	Language	Result	Execution time	Memory
68789		istlemin	parentrises (BOI18_parentrises)	C++14	0 / 100	19 ms	9916 KiB

parentrises

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

string getColoring(string s){
	ll mx = s.size()+2;
    vector<vector<vector<ll>>> color(mx,vector<vi>(mx,vi(mx,0)));

    vector<vector<vector<bool>>> dp(mx,vector<vector<bool>>(mx,vector<bool>(mx,0)));
    //dp[numLeft][rgLevel][bgLevel]
    dp[0][0][0] = true;
    rep(i,1,mx){
        rep(rgLevel,0,mx-1)
			rep(bgLevel,0,mx-1){
				dp[i][rgLevel][bgLevel] = false;
				if(s[i-1]=='('){
					if(rgLevel>0&&dp[i-1][rgLevel-1][bgLevel]){
						dp[i][rgLevel][bgLevel] = true;
						color[i][rgLevel][bgLevel] = 0;
					}
					if(bgLevel>0&&dp[i-1][rgLevel][bgLevel-1]){
						dp[i][rgLevel][bgLevel] = true;
						color[i][rgLevel][bgLevel] = 2;
					}
					if(bgLevel>0&&rgLevel>0&&dp[i-1][rgLevel-1][bgLevel-1]){
						dp[i][rgLevel][bgLevel] = true;
						color[i][rgLevel][bgLevel] = 1;
					}
				} else {
					if(dp[i-1][rgLevel+1][bgLevel]){
						dp[i][rgLevel][bgLevel] = true;
						color[i][rgLevel][bgLevel] = 0;
					}
					if(dp[i-1][rgLevel][bgLevel+1]){
						dp[i][rgLevel][bgLevel] = true;
						color[i][rgLevel][bgLevel] = 2;
					}
					if(dp[i-1][rgLevel+1][bgLevel+1]){
						dp[i][rgLevel][bgLevel] = true;
						color[i][rgLevel][bgLevel] = 1;
					}
				}
                //cout<<i<<" "<<rgLevel<<" "<<bgLevel<<": "<<dp[i][rgLevel][bgLevel]<<endl;
			}
    }
    if(!dp[s.size()][0][0]) return "";
    string ans = s;


    ll rg = 0;
	ll bg = 0;
    for(ll i = s.size();i>0;--i){
        if(color[i][rg][bg]==0) {
			ans[i-1] = 'R';
			if(s[i-1]=='(') rg--;
			else rg++;
        }
        if(color[i][rg][bg]==1) {
			ans[i-1] = 'G';
			if(s[i-1]=='(') bg--;
			else bg++;
			if(s[i-1]=='(') rg--;
			else rg++;
        }
        if(color[i][rg][bg]==2) {
			ans[i-1] = 'B';
			if(s[i-1]=='(') bg--;
			else bg++;
        }
    }
    return ans;
}

void solve1(){
	ll t; cin>>t;
	while(t--){
		string str;
		cin>>str;
		string ans = getColoring(str);
		if(ans=="") cout<<"impossible"<<endl;
		else cout<<ans<<endl;
	}
}

void solve2(){
    /*ll mx = 7;
    ll mod = 1e9+7;

    vector<vector<vi>> dp(mx,vector<vi>(mx,vi(mx,0)));
    //dp[numLeft][rgLevel][bgLevel]
    dp[0][0][0] = 1;
    rep(i,1,mx){
        rep(rgLevel,0,mx-1)
			rep(bgLevel,0,mx-1){
				dp[i][rgLevel][bgLevel] = 0;
                bool bracketToLeft = false;
				if(rgLevel>0&&dp[i-1][rgLevel-1][bgLevel]>) dp[i][rgLevel][bgLevel] += dp[i-1][rgLevel-1][bgLevel];
				if(bgLevel>0) dp[i][rgLevel][bgLevel] += dp[i-1][rgLevel][bgLevel-1];
				if(bgLevel>0&&rgLevel>0) dp[i][rgLevel][bgLevel] += dp[i-1][rgLevel-1][bgLevel-1];
				dp[i][rgLevel][bgLevel] += dp[i-1][rgLevel+1][bgLevel];
				dp[i][rgLevel][bgLevel] += dp[i-1][rgLevel][bgLevel+1];
				dp[i][rgLevel][bgLevel] += dp[i-1][rgLevel+1][bgLevel+1];
                dp[i][rgLevel][bgLevel] = dp[i][rgLevel][bgLevel]%mod;
                cout<<i<<" "<<rgLevel<<" "<<bgLevel<<": "<<dp[i][rgLevel][bgLevel]<<endl;
			}
    }
    ll t; cin>>t;
    rep(i,0,t){
		ll n; cin>>n;
		cout<<dp[n][0][0]<<endl;
    }*/
}

int main(){
	cin.sync_with_stdio(false);
    ll p; cin>>p;
    if(p==2){
		solve2();
    }
    if(p==1){
		solve1();
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 6
• Subtask 4: 0 / 28
• Subtask 5: 0 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28