oj.uz

Submission #511422

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

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

#define MAXN 100005

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

bool solve(int l,int r) {
	if(l > r) return true;
	auto uwu = pos[s[l] - 'a'][mask[l]];
	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();
	mask[0] = 0;
	for(int i = 0;i < N;++i) {
		mask[i + 1] = mask[i] ^ (1 << (s[i] - 'a'));
		pos[s[i] - 'a'][mask[i + 1]].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 304 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 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 304 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -