Submission #255160

#	Time	Username	Problem	Language	Result	Execution time	Memory
255160		amoo_safar	parentrises (BOI18_parentrises)	C++14	50 / 100	69 ms	12552 KiB

parentrises

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

str Solve1(){
	vector<int> O, C;
	int sm = 0;
	str s;
	cin >> s;
	int n = s.size();
	vector<int> mk(n, 0);

	for(int i = 0; i < n; i++){
		if(s[i] == '('){
			O.pb(i);
			sm ++;
		} else {
			C.pb(i);
			sm --;
		}
	}
	reverse(all(C));

	str Im = "impossible";
	int Ao = (sm <= 0 ? -sm: 0);
	int Ac = (sm >= 0 ? sm: 0);

	int idx = -1;
	for(int i = 0; i < n; i++){
		if(Ao + i > O.size()) break;
		if(Ac + i > C.size()) break;
		int po = (Ao + i == 0 ? -1 : O[Ao + i - 1]);
		int pc = (Ac + i == 0 ? n : C[Ac + i - 1]);
		if(po >= pc) break;
		idx = i;
	}
	//debug(idx);
	if(idx == -1) return Im;
	for(int i = 0; i < Ao + idx; i++) mk[O[i]] = 1;
	for(int i = 0; i < Ac + idx; i++) mk[C[i]] = 1;

	str res = "";
	int Sr = 0, Sb = 0;
	for(int i = 0; i < n; i++){
		if(mk[i]){
			res += "G";
			if(s[i] == '('){
				Sr ++;
				Sb ++;
			} else {
				Sr --;
				Sb --;
			}
		} else {
			if(s[i] == '('){
				if(Sr < Sb) Sr ++, res += "R";
				else Sb ++, res += "B";
			} else {
				if(Sr > Sb) Sr --, res += "R";
				else Sb --, res += "B";
			}
		}
		if(min(Sr, Sb) < 0) return Im;
	}

	assert(Sr == 0); assert(Sb == 0);
	return res;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int PR;
	cin >> PR;
	assert(PR == 1);
	int T;
	cin >> T;
	while(T --){
		cout << Solve1() << '\n';
	}
	return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'str Solve1()':
parentrises.cpp:47:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(Ao + i > O.size()) break;
      ~~~~~~~^~~~~~~~~~
parentrises.cpp:48:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(Ac + i > C.size()) break;
      ~~~~~~~^~~~~~~~~~

• 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