Submission #244580

#	Time	Username	Problem	Language	Result	Execution time	Memory
244580		tonowak	Match (CEOI16_match)	C++17	100 / 100	38 ms	17708 KiB

match

#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;
	int n = size(s);
	vector<int> value(n);
	REP(i, n)
		value[i] = int(s[i] - 'a');

#ifdef DEBUG
	constexpr int alpha = int('c' - 'a' + 1);
#else
	constexpr int alpha = int('z' - 'a' + 1);
#endif
	using BS = bitset<alpha>;
	BS empty;
	vector<BS> prefix(n);

	vector<vector<int>> best_start(n, vector<int>(alpha, -1));
	FOR(i, 2, n - 1) {
		REP(c, alpha) {
			if(value[i] == value[i - 1] and value[i - 2] == c)
				best_start[i][c] = i - 1;
			else {
				if(value[i] == value[i - 1])
					best_start[i][c] = best_start[i - 2][c];
				int l = best_start[i - 1][value[i]];
				if(l == -1)
					continue;
				assert(l != 0);
				--l;
				if(l == 0)
					continue;
				--l;

				if(value[l] == c)
					best_start[i][c] = max(best_start[i][c], l + 1);
				else
					best_start[i][c] = max(best_start[i][c], best_start[l][c]);
			}
		}
		REP(c, alpha)
			debug(i, c, best_start[i][c]);
	}

	auto possible = [&](int l, int r) {
		vector<int> sztos;
		FOR(i, l, r)
			if(size(sztos) and sztos.back() == value[i])
				sztos.pop_back();
			else
				sztos.emplace_back(value[i]);
		return size(sztos) == 0;
	};

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

	vector<int> answer(n, -1);
	function<void (int, int)> divconq = [&](int l, int r) {
		if(l > r)
			return;
		if(value[l] == value[r]) {
			assert(answer[l] == -1 and answer[r] == -1);
			answer[l] = 0;
			answer[r] = 1;
			divconq(l + 1, r - 1);
			return;
		}
		int split_r = best_start[r][value[l]] - 1;
		debug(l, r, split_r);
		assert(answer[l] == -1 and answer[split_r] == -1);
		answer[l] = 0;
		answer[split_r] = 1;
		divconq(l + 1, split_r - 1);
		divconq(split_r + 1, r);
	};
	divconq(0, n - 1);

	REP(i, n)
		assert(answer[i] != -1);
	for(int b : answer)
		cout << (b ? ')' : '(');
	cout << '\n';
}

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