Submission #365391

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
365391	2021-02-11T15:12:03 Z	tfg	parentrises (BOI18_parentrises)	C++17	50 / 100	78 ms	15380 KB

parentrises

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

bool good(const std::string &str) {
	int bal = 0;
	for(auto ch : str) {
		bal += ch == '(' ? 1 : -1;
		if(bal < 0) return false;
	}
	return bal == 0;
}

void solve1() {
	int t;
	std::cin >> t;
	while(t--) {
		std::string str;
		std::cin >> str;
		int n = (int) str.size();
		std::vector<int> pos[2];
		std::vector<int> col(n, 3);
		int bst = 0, sum = 0;
		for(int i = 0; i < n; i++) {
			pos[str[i] == '('].push_back(i);
			sum += str[i] == '(' ? 1 : -1;
			bst = std::min(bst, sum);
		}
		int bal = (int) pos[1].size() - (int) pos[0].size();
		if(bst < 0) {
			bal -= bst;
			bst = -bst;
			for(int i = 0; i < 2*bst && i < (int) pos[0].size(); i++) {
				col[pos[0][i]] = i % 2 == 0 ? 1 : 2;
			}
		}
		if(bal > 0) {
			for(int i = 0; i < 2*bal && i < (int) pos[1].size(); i++) {
				col[pos[1][(int) pos[1].size() - i - 1]] = i % 2 == 0 ? 1 : 2;
			}
		}
		
		std::string haha[2];
		for(int i = 0; i < n; i++) {
			if(col[i] & 1) haha[0] += str[i];
			if(col[i] & 2) haha[1] += str[i];
		}
		if(good(haha[0]) && good(haha[1])) {
			for(int i = 0; i < n; i++) {
				char ch;
				if(col[i] == 3) {
					ch = 'G';
				} else if(col[i] == 1) {
					ch = 'R';
				} else {
					ch = 'B';
				}
				std::cout << ch;
			}
			std::cout << '\n';
		} else {
			std::cout << "impossible\n";
		}
	}
}

void solve2() {

}

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int P;
	std::cin >> P;
	if(P == 1) {
		solve1();
	} else {
		solve2();
	}
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct

Subtask #2

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct

Subtask #4

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	1 ms	492 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	512 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	7 ms	620 KB	Output is correct
17	Correct	8 ms	1860 KB	Output is correct
18	Correct	7 ms	716 KB	Output is correct
19	Correct	7 ms	1408 KB	Output is correct
20	Correct	8 ms	1768 KB	Output is correct
21	Correct	67 ms	2284 KB	Output is correct
22	Correct	77 ms	15356 KB	Output is correct
23	Correct	58 ms	3428 KB	Output is correct
24	Correct	63 ms	7800 KB	Output is correct
25	Correct	78 ms	15380 KB	Output is correct

Subtask #5

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	364 KB	Unexpected end of file - int32 expected

Subtask #6

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	364 KB	Unexpected end of file - int32 expected

Subtask #7

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	364 KB	Unexpected end of file - int32 expected