Submission #511451

#	Time	Username	Problem	Language	Result	Execution time	Memory
511451		CodeTiger927	Match (CEOI16_match)	C++17	100 / 100	75 ms	38588 KiB

match

using namespace std;

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

#define MAXN 100005
#define MOD 998244353

int N,pre0[MAXN],pre1[MAXN],mask[MAXN];
string s;
char ans[MAXN];
map<long long,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();
	long long uwu = 0;
	mask[0] = 0;
	stack<int> st;
	for(int i = 0;i < N;++i) {
		if(st.size() && s[i] == s[st.top()]) {
			mask[i + 1] = (mask[i] + MOD - (st.size() * (1 << (s[st.top()] - 'a')) % MOD)) % MOD;
			st.pop();
		}else{
			st.push(i);
			mask[i + 1] = (mask[i] + st.size() * (1 << (s[i] - 'a'))) % MOD;
		}
		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;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:33:12: warning: unused variable 'uwu' [-Wunused-variable]
   33 |  long long uwu = 0;
      |            ^~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63