oj.uz

답안 #365391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
365391 2021-02-11T15:12:03 Z tfg parentrises (BOI18_parentrises) C++17
50 / 100
 78 ms 15380 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected