Submission #59746

#	Time	Username	Problem	Language	Result	Execution time	Memory
59746		model_code	parentrises (BOI18_parentrises)	C++17	50 / 100	224 ms	8732 KiB

parentrises

#include <bits/stdc++.h>

using namespace std;

string solve(const string &test) {
	const int N = test.size();

	string  redMask(N, ' ');
	string blueMask(N, ' ');

	vector <int> redStk;
	queue <int> redOpened;
	for (int i = 0; i < N; ++ i) {
		const char ch = test[i];
		if (ch == '(') {
			redMask[i] = 'R';
			redStk.push_back(i);
			redOpened.push(i);
		}
		else if (ch == ')') {
			if (!redStk.empty()) {
				redMask[i] = 'R';
				redStk.pop_back();
			}
			else if (redOpened.empty())
				return "impossible";
			else {
				blueMask[i] = 'B';
				blueMask[redOpened.front()] = 'B';
				redOpened.pop();
			}
		}
	}

	reverse(redStk.begin(), redStk.end());
	stack <int> redClosed;

	int i = N - 1;
	for (const int pos: redStk) {
		while (i > pos) {
			if (test[i] == ')')
				redClosed.push(i);
			-- i;
		}
		if (redClosed.empty())
			return "impossible";
		else {
			redMask[pos]  = ' ';
			blueMask[pos] = 'B';

			const int transformToGreen = redClosed.top();
			redClosed.pop();
			blueMask[transformToGreen] = 'B';
		}
	}

	string coloring;
	for (i = 0; i < N; ++ i)
		if (redMask[i] == 'R' && blueMask[i] == 'B')
			coloring += 'G';
		else if (redMask[i] == 'R')
			coloring += 'R';
		else if (blueMask[i] == 'B')
			coloring += 'B';
		else
			assert(0);
	return coloring;
}

int main() {
	int type; cin >> type;
	if (type == 2) {
            return 0;
        }

	int T;
	cin >> T;
	while (T --) {
		// Read test
		string str;
		cin >> str;
		
		// Check validity
		assert(1 <= str.size() && str.size() <= 1000000);
		for (auto it: str)
			assert(it == '(' || it == ')');
		cout << solve(str) << '\n';
	}
	return 0;
}

• 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