oj.uz

Submission #244580

# Submission time Handle Problem Language Result Execution time Memory
244580 2020-07-04T10:09:16 Z tonowak Match (CEOI16_match) C++17
100 / 100
 38 ms 17708 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 7 ms 1280 KB Output is correct
9 Correct 7 ms 1536 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 6 ms 1536 KB Output is correct
12 Correct 23 ms 10624 KB Output is correct
13 Correct 22 ms 11520 KB Output is correct
14 Correct 26 ms 12844 KB Output is correct
15 Correct 33 ms 14456 KB Output is correct
16 Correct 35 ms 14464 KB Output is correct
17 Correct 31 ms 15360 KB Output is correct
18 Correct 38 ms 14840 KB Output is correct
19 Correct 32 ms 16376 KB Output is correct
20 Correct 22 ms 11064 KB Output is correct
21 Correct 35 ms 17708 KB Output is correct