Submission #96686

#	Time	Username	Problem	Language	Result	Execution time	Memory
96686		jasony123123	Match (CEOI16_match)	C++11	100 / 100	17 ms	11128 KiB

match

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63