oj.uz

Submission #609167

# Submission time Handle Problem Language Result Execution time Memory
609167 2022-07-27T12:37:50 Z AkramElOmrani Match (CEOI16_match) C++17
100 / 100
 1498 ms 3620 KB 
#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();
	vector<int> st(n + 1);
	string ans(n, '?');
	function<bool(int, int)> can = [&](int l, int r) {
		int last = 0;
		if(l > r) return true;
		if((r - l + 1) & 1) return false;
		if(s[l] == s[r]) {
			ans[l] = '(', ans[r] = ')';
			return can(l + 1, r - 1);
		}
		for(int i = r; l <= i; --i) {
			if(!last || st[last - 1] != s[i]) st[last++] = s[i];
			else {
				--last;
				if(last <= 0 && l < i - 1 && s[l] == s[i - 1]) {
					ans[l] = '(', ans[i - 1] = ')';
					return can(l + 1, i - 2) && can(i, r);
				}
			}
		}
		return false;
	};
	if(can(0, n - 1)) {
		cout << ans;
	} else {
		cout << -1;
	}
	cout << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 6 ms 436 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 52 ms 2088 KB Output is correct
13 Correct 24 ms 2164 KB Output is correct
14 Correct 409 ms 2844 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 3 ms 3412 KB Output is correct
17 Correct 57 ms 3532 KB Output is correct
18 Correct 7 ms 1996 KB Output is correct
19 Correct 706 ms 2932 KB Output is correct
20 Correct 255 ms 2604 KB Output is correct
21 Correct 1498 ms 3620 KB Output is correct