oj.uz

Submission #68794

# Submission time Handle Problem Language Result Execution time Memory
68794 2018-08-18T12:07:32 Z istlemin parentrises (BOI18_parentrises) C++14
16 / 100
 535 ms 263168 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,-1)));

    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-1){
        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<<": "<<color[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++;
        } else if(color[i][rg][bg]==1) {
			ans[i-1] = 'G';
			if(s[i-1]=='(') bg--;
			else bg++;
			if(s[i-1]=='(') rg--;
			else rg++;
        } else 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 3 ms 724 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5624 KB Output is correct
2 Correct 25 ms 10104 KB Output is correct
3 Correct 4 ms 10104 KB Output is correct
4 Correct 7 ms 10104 KB Output is correct
5 Correct 21 ms 10172 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5624 KB Output is correct
2 Correct 25 ms 10104 KB Output is correct
3 Correct 4 ms 10104 KB Output is correct
4 Correct 7 ms 10104 KB Output is correct
5 Correct 21 ms 10172 KB Output is correct
6 Runtime error 535 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5624 KB Output is correct
2 Correct 25 ms 10104 KB Output is correct
3 Correct 4 ms 10104 KB Output is correct
4 Correct 7 ms 10104 KB Output is correct
5 Correct 21 ms 10172 KB Output is correct
6 Runtime error 535 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.