oj.uz

Submission #134146

# Submission time Handle Problem Language Result Execution time Memory
134146 2019-07-22T07:04:16 Z 송준혁(#3232) Match (CEOI16_match) C++14
37 / 100
 61 ms 8440 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N;
char str[2020], ans[2020];
bool P[2020][2020];
vector<char> ST;

void f(int s, int e){
	if (s >= e) return;
	for (int i=e; i>s; i--){
		if (str[s] == str[i] && P[s+1][i-1] && P[i+1][e]){
			ans[s] = '(', ans[i] = ')';
			f(s+1, i-1); f(i+1, e);
			return;
		}
	}
}

int main(){
	scanf("%s", str+1);
	N = strlen(str+1);
	memset(P, true, sizeof P);
	for (int i=1; i<=N; i++){
		ST.clear();
		for (int j=i; j<=N; j++){
			if (!ST.empty() && ST.back() == str[j]) ST.pop_back();
			else ST.push_back(str[j]);
			if (!ST.empty()) P[i][j] = false;
		}
	}
	if (!P[1][N]){
		puts("-1");
		return 0;
	}
	f(1, N);
	printf("%s\n", ans+1);
	return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:23: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 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4344 KB Output is correct
4 Correct 6 ms 4344 KB Output is correct
5 Correct 7 ms 4344 KB Output is correct
6 Correct 11 ms 4344 KB Output is correct
7 Correct 11 ms 4344 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4344 KB Output is correct
4 Correct 6 ms 4344 KB Output is correct
5 Correct 7 ms 4344 KB Output is correct
6 Correct 11 ms 4344 KB Output is correct
7 Correct 11 ms 4344 KB Output is correct
8 Runtime error 61 ms 8440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -