Submission #861875

#	Time	Username	Problem	Language	Result	Execution time	Memory
861875		maks007	parentrises (BOI18_parentrises)	C++14	0 / 100	1 ms	344 KiB

parentrises

#include "bits/stdc++.h"

using namespace std;

#define int long long

pair <int,int> mn(pair <int,int> a, pair <int,int> b) {
	if(max(a.first, a.second) < max(b.first, b.second) ) return a;
	return b;
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	int q;
	cin >> q;
	while(q --) {
		string str;
		cin >> str;
		int n = (int)str.size();
		// pair <int,int> dp[n][3];
		// for(int i = 0; i < n; i ++) {
		// 	for(int j = 0; j < 3; j ++) dp[i][j] = {1e9,1e9};
		// }
		// for(int i = 0; i < n; i ++) { // 0 - red, 1 - blue, 2 - green
		// 	if(!i) {
		// 		if(str[i] == ')') {
		// 			cout << "impossible\n";
		// 			goto end;
		// 		}else {
		// 			dp[i][0] = {1, 0};
		// 			dp[i][1] = {0, 1};
		// 			dp[i][2] = {1, 1};
		// 		}
		// 	}else {
		// 		if(str[i] == ')') {
		// 			for(int j = 0; j < 3; j ++) {
		// 				if(min(dp[i-1][j].first, dp[i-1][j].second) > 0) {
		// 					dp[i][2] = mn(dp[i][j], make_pair(dp[i-1][j].first-1, dp[i-1][j].second-1));
		// 				} 
		// 				if(dp[i-1][j].first > 0) {
		// 					dp[i][0] = mn(dp[i][j], make_pair(dp[i-1][j].first - 1, dp[i-1][j].second));
		// 				}
		// 				if(dp[i-1][j].second > 0) {
		// 					dp[i][1] = mn(dp[i][j], make_pair(dp[i-1][j].first, dp[i-1][j].second - 1));
		// 				}
		// 			}
		// 			if(dp[i][0].first == 1e9 && dp[i][1].first == 1e9 && dp[i][2].first == 1e9) {
		// 				cout << "impossible\n";
		// 				goto end;
		// 			}
		// 		}else {
		// 			for(int j = 0; j < 3; j ++) {
		// 				dp[i][2] = mn(dp[i][2], {dp[i-1][j].first + 1, dp[i-1][j].second + 1});
		// 				dp[i][0] = mn(dp[i][0], {dp[i-1][j].first + 1, dp[i-1][j].second});
		// 				dp[i][1] = mn(dp[i][1], {dp[i-1][j].first, dp[i-1][j].second + 1});
		// 			}
		// 		}
		// 	}
		// }
		// if(dp[n-1][0].first == 0 && dp[n-1][2].second == 0) cout << "possible\n";
		// else if(dp[n-1][0].first == 0 && dp[n-1][2].second == 0) cout << "possible\n";
		// else if(dp[n-1][0].first == 0 && dp[n-1][2].second == 0) cout << "possible\n";
		// else cout << "impossible\n";
		// end:;
		// continue;
		vector <pair <int,int>> sequence;
		int cnt = 1;
		for(int i = 1; i < n; i ++) {
			if(str[i] == str[i - 1]) {
				cnt ++;
			}else {
				sequence.push_back({cnt, (str[i-1] == '(')});
				cnt = 1;
			}
		}
		if(cnt) {
			sequence.push_back({cnt, (str[n-1] == '(')});
		}
		if(sequence.size() % 2 == 1) {
			cout << "impossible\n";
			continue;
		}
		if(sequence[0].second == -1) {
			cout << "impossible\n";
			continue;
		}
		string ans;
		for(int i = 0; i < sequence.size()-1; i += 2) {
			int v = sequence[i].first, u = sequence[i+1].first;
			if(v == u) {
				v += u;
				while(v --) ans += 'G';
			}
			else if(v * 2 == u) {
				while(v --) ans += 'G';
				int U = u;
				u/=2;
				while(u --) ans += 'R';
				u = U;
				u /= 2;
				while(u --) ans += 'B';
			}else if(u * 2 == v) {
				int V = v;
				v/=2;
				while(v --) ans += 'R';
				v = V;
				v /= 2;
				while(v --) ans += 'B';
				while(u --) ans += 'G';
			}else {
				cout << "impossible\n";
				goto end;
			}
		}
		cout << ans << "\n";
		end:;
		continue;
	}
	return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:91:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i = 0; i < sequence.size()-1; i += 2) {
      |                  ~~^~~~~~~~~~~~~~~~~~~

• 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