oj.uz

Submission #68789

# Submission time Handle Problem Language Result Execution time Memory
68789 2018-08-18T11:38:21 Z istlemin parentrises (BOI18_parentrises) C++14
0 / 100
 19 ms 9916 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5496 KB Output is correct
2 Incorrect 19 ms 9916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5496 KB Output is correct
2 Incorrect 19 ms 9916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5496 KB Output is correct
2 Incorrect 19 ms 9916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9916 KB Unexpected end of file - int32 expected

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9916 KB Unexpected end of file - int32 expected

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9916 KB Unexpected end of file - int32 expected