Submission #128337

#	Time	Username	Problem	Language	Result	Execution time	Memory
128337		Vardanyan	Match (CEOI16_match)	C++14	10 / 100	2047 ms	632 KiB

match

#include <iostream>
#include <bitset>
#include <string>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <map>
using namespace std;
const int N = 100 * 1000 + 5;
int p[N][30];
string s;
string ans;
void rec(int l, int r) {
	if (l >= r) return;
	if (r - l == 1) {
		ans[l] = '(';
		ans[r] = ')';
		return;
	}
	if (s[l] == s[r]) {
		ans[l] = '(';
		ans[r] = ')';
		rec(l + 1, r - 1);
		return;
	}
	int pos = p[r][s[l] - 'a'];
	ans[l] = '(';
	ans[pos] = ')';
	if (r - l <= 1) return;
	rec(l + 1, pos - 1);
	rec(pos + 1, r);
}
long long pw[1000 * 100 + 5];
const int MOD = 1000 * 1000 * 1000 + 7;
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("7-router.out","w",stdout);
	cin >> s;
	stack<char> st;
	for (int i = 0; i<s.length(); i++) {
		ans += "x";
		if (!st.size()) {
			st.push(s[i]);
			continue;
		}
		else {
			char c = st.top();
			if (c == s[i]) {
				st.pop();
				continue;
			}
			st.push(s[i]);
		}
	}
	if (st.size()) {
		cout << -1 << endl;
		return 0;
	}
	pw[0] = 1;
	for (int i = 1; i <= s.length(); i++) {
		pw[i] = pw[i - 1] * 259;
		pw[i] %= MOD;
	}
	long long hsh = 0;
	map<long long, int> mp;
	map<long long, bool> bl;
	for (int i = 0; i<s.length(); i++) {
		if (!st.size()) {
			st.push(s[i]);
			hsh += (pw[st.size()] * (s[i] - 'a' + 1));
			hsh %= MOD;
			int x = mp[hsh];
			if (bl[hsh]) {
				p[i][s[x] - 'a'] = x;
			}
			mp[hsh] = i;
			bl[hsh] = 1;
			continue;
		}
		char c = st.top();
		if (c == s[i]) {
			hsh -= (pw[st.size()] * (s[i] - 'a' + 1));
			 hsh += ((long long)30*MOD);
			 hsh %= MOD;
			st.pop();
		}
		else {
			st.push(s[i]);
			hsh += (pw[st.size()] * (s[i] - 'a' + 1));
			hsh %= MOD;
		}
		int x = mp[hsh];
		if (bl[hsh]) {
			p[i][s[x] - 'a'] = x;
		}
		mp[hsh] = i;
		bl[hsh] = 1;
	}
	/*for (int j = 0; j<s.length(); j++) {
	for (int i = 0; i<2; i++) cout << p[j][i] << " ";
	cout << endl;
	}*/
	rec(0, s.length() - 1);
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<s.length(); i++) {
                  ~^~~~~~~~~~~
match.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= s.length(); i++) {
                  ~~^~~~~~~~~~~~~
match.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<s.length(); i++) {
                  ~^~~~~~~~~~~

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