Submission #609271

#	Time	Username	Problem	Language	Result	Execution time	Memory
609271		AkramElOmrani	Match (CEOI16_match)	C++17	100 / 100	25 ms	15804 KiB

match

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ios ios_base::sync_with_stdio(0);cin.tie(0);

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int gen(int a, int b) {return (ll)rng() % (b - a + 1) + a;}

const int alp = 26;

int main()
{
	ios
	string s; cin >> s;
	int n = s.length();
	stack<char> st;
	for(char c : s) {
		if(!st.empty() && st.top() == c) {
			st.pop();
		} else {
			st.push(c);
		}
	}
	if(!st.empty()) {
		cout << -1;
		return 0;
	}
	vector<vector<int>> after(n, vector<int>(alp));
	for(int i = 0; i < n; ++i) {
		int last = -1;
		if(i > 0) {
			last = after[i - 1][s[i] - 'a'];
		}
		for(int p = 0; p < alp; ++p) {
			if(s[i] - 'a' == p) after[i][p] = i;
			else {
				if(last > 0) {
					after[i][p] = after[last - 1][p];
				} else {
					after[i][p] = -1;
				}
			}
		}
	}
	function<void(int, int)> rec = [&](int l, int r) {
		if(l > r) return;
		int mid = after[r][s[l] - 'a'];
		// cas of s[l] - 'a' and both of them are equal
		s[l] = '(';
		s[mid] = ')';
		rec(l + 1, mid - 1), rec(mid + 1, r);
	};
	rec(0, n - 1);
	cout << s << '\n';
}

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