oj.uz

Submission #128354

# Submission time Handle Problem Language Result Execution time Memory
128354 2019-07-10T18:59:54 Z Vardanyan Match (CEOI16_match) C++14
37 / 100
 2000 ms 353656 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 = 500 * 1000+7;
 vector<int>  g[30][MOD];
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 355 ms 352760 KB Output is correct
2 Correct 365 ms 352760 KB Output is correct
3 Correct 367 ms 352760 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 352760 KB Output is correct
2 Correct 365 ms 352760 KB Output is correct
3 Correct 367 ms 352760 KB Output is correct
4 Correct 339 ms 352672 KB Output is correct
5 Correct 370 ms 352888 KB Output is correct
6 Correct 385 ms 352856 KB Output is correct
7 Correct 337 ms 352868 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 352760 KB Output is correct
2 Correct 365 ms 352760 KB Output is correct
3 Correct 367 ms 352760 KB Output is correct
4 Correct 339 ms 352672 KB Output is correct
5 Correct 370 ms 352888 KB Output is correct
6 Correct 385 ms 352856 KB Output is correct
7 Correct 337 ms 352868 KB Output is correct
8 Execution timed out 2060 ms 353656 KB Time limit exceeded
9 Halted 0 ms 0 KB -