oj.uz

Submission #511409

# Submission time Handle Problem Language Result Execution time Memory
511409 2022-01-15T18:31:21 Z CodeTiger927 Match (CEOI16_match) C++17
10 / 100
 1 ms 332 KB 
using namespace std;

#include <iostream>
#include <vector>
#include <algorithm>

#define MAXN 100005

int N,pre0[MAXN],pre1[MAXN];
string s;
char ans[MAXN];
vector<int> pos[2][2][26];

bool solve(int l,int r) {
	if(l > r) return true;
	auto uwu = pos[pre0[l]][pre1[l]][s[l] - 'a'];
	auto it = upper_bound(uwu.begin(),uwu.end(),r);
	if(it == uwu.begin() || *prev(it) <= l) return false;
	int owo = *prev(it);
	// cout << l << " " << owo << endl;
	ans[l] = '(';
	ans[owo] = ')';
	if(l == r - 1) return true;
	return solve(l + 1,owo - 1) & solve(owo + 1,r);
}

int main() {
	cin >> s;
	N = s.length();
	pre0[0] = pre1[0] = 0;
	for(int i = 0;i < N;++i) {
		pre0[i + 1] = pre0[i];
		pre1[i + 1] = pre1[i];
		if(s[i] == 'a') {
			pre0[i + 1] ^= 1;
		}else{
			pre1[i + 1] ^= 1;
		}
		pos[pre0[i + 1]][pre1[i + 1]][s[i] - 'a'].push_back(i);
	}
	if(solve(0,N - 1)) {
		for(int i = 0;i < N;++i) {
			cout << ans[i];
		}
		cout << endl;
	}else{
		cout << -1 << endl;
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 308 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -