oj.uz

Submission #128351

# Submission time Handle Problem Language Result Execution time Memory
128351 2019-07-10T18:58:35 Z Vardanyan Match (CEOI16_match) C++14
100 / 100
 1373 ms 99000 KB 
#include <bits/stdc++.h>
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'+1];
	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;
map<long long, vector<int> > g[30];
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;
	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;
			}*/
			for (int ii = 1; ii <= 26; ii++) {
				for (int j = 0; j < g[ii][hsh].size(); j++) {
					p[i][ii] = max(p[i][ii], g[ii][hsh][j]);
				}
			}
			g[s[i]-'a'+1][hsh].push_back(i);
			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;
		}*/
		for (int ii = 1; ii <= 26; ii++) {
			for (int j = 0; j < g[ii][hsh].size(); j++) {
				p[i][ii] = max(p[i][ii], g[ii][hsh][j]);
			}
		}
		g[s[i] - 'a' + 1][hsh].push_back(i);
	}
	/*for (int j = 0; j<s.length(); j++) {
	for (int i = 1; i<=2; i++) cout << p[j][i] << " ";
	cout << endl;
	}*/
	rec(0, s.length() - 1);
	cout << ans << endl;
	return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<s.length(); i++) {
                  ~^~~~~~~~~~~
match.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= s.length(); i++) {
                  ~~^~~~~~~~~~~~~
match.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<s.length(); i++) {
                  ~^~~~~~~~~~~
match.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < g[ii][hsh].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~~
match.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[ii][hsh].size(); j++) {
                    ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 1148 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 664 KB Output is correct
7 Correct 10 ms 1532 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 1148 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 664 KB Output is correct
7 Correct 10 ms 1532 KB Output is correct
8 Correct 32 ms 5400 KB Output is correct
9 Correct 37 ms 6520 KB Output is correct
10 Correct 46 ms 8056 KB Output is correct
11 Correct 48 ms 7928 KB Output is correct
12 Correct 807 ms 68256 KB Output is correct
13 Correct 912 ms 73724 KB Output is correct
14 Correct 882 ms 77856 KB Output is correct
15 Correct 587 ms 11636 KB Output is correct
16 Correct 580 ms 11896 KB Output is correct
17 Correct 664 ms 55452 KB Output is correct
18 Correct 480 ms 13472 KB Output is correct
19 Correct 1373 ms 99000 KB Output is correct
20 Correct 792 ms 67968 KB Output is correct
21 Correct 1327 ms 97316 KB Output is correct