Submission #255154

#	Time	Username	Problem	Language	Result	Execution time	Memory
255154		Saboon	parentrises (BOI18_parentrises)	C++14	50 / 100	151 ms	11284 KiB

parentrises

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 10;

int l[maxn], r[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int type;
	cin >> type;
	if (type == 1){
		int tc;
		cin >> tc;
		while (tc --){
			string s;
			cin >> s;
			int L = 0, R = 0;
			int n = s.size();
			bool flag = 0;
			for (int i = n-1; i >= 0; i--){
				if (s[i] == ')')
					L ++, R += 2;
				else{
					if (R == 0){
						flag = 1;
						break;
					}
					L = max(0, L-2);
					R --;
				}
				l[i] = L, r[i] = R;
			}
			if (flag == 1 or L > 0){
				cout << "impossible\n";
				continue;
			}
			l[n] = r[n] = 0;
			int now = 0;
			bool Red1 = 1, Red2 = 1; 
			for (int i = 0; i < n; i++){
				if (s[i] == '('){
					if (l[i+1] <= now+1 and now+1 <= r[i+1]){
						if (Red1)
							cout << 'R';
						else
							cout << 'B';
						Red1 ^= 1;
						now ++;
					}
					else{
						cout << 'G';
						now += 2;
					}
				}
				else{
					if (l[i+1] <= now-1 and now-1 <= r[i+1]){
						if (Red2)
							cout << 'R';
						else
							cout << 'B';
						Red2 ^= 1;
						now --;
					}
					else{
						cout << 'G';
						now -= 2;
					}
				}
			}
			cout << '\n';
		}
	}
}

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