oj.uz

Submission #96686

# Submission time Handle Problem Language Result Execution time Memory
96686 2019-02-10T20:58:13 Z jasony123123 Match (CEOI16_match) C++11
100 / 100
 17 ms 11128 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll INF = 1e14;
/***********************CEOI 2016 D2 Match*****************************************/

int N;
string S, ans;
int pre[100000][26];

void assign(int lo, int hi) {
	if (lo >= hi) return;

	if (S[hi] == S[lo]) {
		ans[lo] = '(', ans[hi] = ')';
		assign(lo + 1, hi - 1);
	}
	else {
		int mid = pre[hi][S[lo] - 'a'];
		assert(lo < mid);
		ans[lo] = '(', ans[mid] = ')';
		assign(lo + 1, mid - 1), assign(mid + 1, hi);
	}
}

bool possible() {
	stack<char> stac;
	FOR(i, 0, N) {
		if (stac.empty() || stac.top() != S[i])
			stac.push(S[i]);
		else
			stac.pop();
	}
	return stac.empty();
}

int main() {
	io();
	cin >> S;
	N = S.size();
	ans.resize(N);

	if (!possible()) {
		cout << "-1\n";
		return 0;
	}

	FOR(c, 0, 26)
		pre[0][c] = -1;

	FOR(i, 1, N) FOR(c, 0, 26) {
		if (S[i] == S[i - 1]) {
			if (0 <= i - 2 && S[i - 2] - 'a' == c)
				pre[i][c] = i - 2;
			else {
				if (i - 2 < 0)
					pre[i][c] = -1;
				else
					pre[i][c] = pre[i - 2][c];
			}
		}
		else {
			int y = pre[i - 1][S[i] - 'a'];
			if (y - 1 < 0)
				pre[i][c] = -1;
			else if (S[y - 1] - 'a' == c)
				pre[i][c] = y - 1;
			else
				pre[i][c] = pre[y - 1][c];
		}
	}

	//FOR(i, 0, N) {
	//	FOR(c, 0, 2) {
	//		cout << i << " " << char(c + 'a') << " = " << pre[i][c] << "\n";
	//	}
	//}

	assign(0, N - 1);
	cout << ans << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 676 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 3 ms 1144 KB Output is correct
12 Correct 11 ms 6780 KB Output is correct
13 Correct 12 ms 7260 KB Output is correct
14 Correct 13 ms 7900 KB Output is correct
15 Correct 13 ms 8824 KB Output is correct
16 Correct 13 ms 8824 KB Output is correct
17 Correct 14 ms 9464 KB Output is correct
18 Correct 14 ms 9852 KB Output is correct
19 Correct 17 ms 10488 KB Output is correct
20 Correct 10 ms 6776 KB Output is correct
21 Correct 17 ms 11128 KB Output is correct