oj.uz

Submission #53520

# Submission time Handle Problem Language Result Execution time Memory
53520 2018-06-30T06:57:32 Z baactree Match (CEOI16_match) C++17
10 / 100
 2000 ms 2052 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
char str[100005];
vector<int> p[256][256];
int s[100005];
void solve(int le, int ri) {
	if (le > ri)return;
	auto it = upper_bound(p[s[le - 1]][str[le]].begin(), p[s[le - 1]][str[le]].end(), ri);
	if (it == p[s[le - 1]][str[le]].begin())while (true);
	int i = *(--it);
	str[le] = '(';
	str[i] = ')';
	solve(le + 1, i - 1);
	solve(i + 1, ri);
	return;
}
int main() {
	scanf("%s", str + 1);
	n = strlen(str + 1);
	stack<int> st;
	for (int i = 1; i <= n; i++) {
		if (!st.empty() && st.top() == str[i])st.pop();
		else st.push(str[i]);
	}
	if (!st.empty())return !printf("-1\n");
	for (int i = 0; i <= n; i++) {
		if (!st.empty()&&st.top() == str[i])st.pop();
		else st.push(str[i]);
		p[st.top()][str[i]].push_back(i);
		s[i] = st.top();
	}
	solve(1, n);
	printf("%s\n", str + 1);
	return 0;
}

Compilation message

match.cpp: In function 'void solve(int, int)':
match.cpp:9:44: warning: array subscript has type 'char' [-Wchar-subscripts]
  auto it = upper_bound(p[s[le - 1]][str[le]].begin(), p[s[le - 1]][str[le]].end(), ri);
                                            ^
match.cpp:9:75: warning: array subscript has type 'char' [-Wchar-subscripts]
  auto it = upper_bound(p[s[le - 1]][str[le]].begin(), p[s[le - 1]][str[le]].end(), ri);
                                                                           ^
match.cpp:10:32: warning: array subscript has type 'char' [-Wchar-subscripts]
  if (it == p[s[le - 1]][str[le]].begin())while (true);
                                ^
match.cpp: In function 'int main()':
match.cpp:30:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   p[st.top()][str[i]].push_back(i);
                     ^
match.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str + 1);
  ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 2024 KB Output is correct
3 Correct 3 ms 2052 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 2024 KB Output is correct
3 Correct 3 ms 2052 KB Output is correct
4 Execution timed out 2080 ms 2052 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB Output is correct
2 Correct 3 ms 2024 KB Output is correct
3 Correct 3 ms 2052 KB Output is correct
4 Execution timed out 2080 ms 2052 KB Time limit exceeded
5 Halted 0 ms 0 KB -