oj.uz

Submission #62219

# Submission time Handle Problem Language Result Execution time Memory
62219 2018-07-27T21:57:50 Z kingpig9 Match (CEOI16_match) C++11
37 / 100
 2000 ms 1200 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
string S;
string ans;

bool good (string seq) {
	stack<int> stk;
	for (int i = 0; i < seq.size(); i++) {
		if (seq[i] == '(') {
			stk.push(i);
		} else {
			if (stk.empty() || S[stk.top()] != S[i]) {
				return false;
			}
			stk.pop();
		}
	}

	for (int i = seq.size(); i < N; i++) {
		//see if you can assign more stuff
		if (!stk.empty() && S[stk.top()] == S[i]) {
			stk.pop();
		} else {
			stk.push(i);
		}
	}
	return stk.empty();
}

int main() {
	if (fopen("match.in", "r")) {
		freopen("match.in", "r", stdin);
		freopen("match.out", "w", stdout);
	}
	cin >> S;
	N = S.size();
	if (!good("")) {
		cout << "-1\n";
		return 0;
	}

	for (int i = 0; i < N; i++) {
		ans += '(';
		if (!good(ans)) {
			ans.back() = ')';
		}
	}
	cout << ans << endl;
}

Compilation message

match.cpp: In function 'bool good(std::__cxx11::string)':
match.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seq.size(); i++) {
                  ~~^~~~~~~~~~~~
match.cpp: In function 'int main()':
match.cpp:45:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("match.in", "r", stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
match.cpp:46:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("match.out", "w", stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 7 ms 496 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 11 ms 552 KB Output is correct
7 Correct 22 ms 576 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 7 ms 496 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 11 ms 552 KB Output is correct
7 Correct 22 ms 576 KB Output is correct
8 Correct 319 ms 740 KB Output is correct
9 Correct 407 ms 768 KB Output is correct
10 Correct 260 ms 768 KB Output is correct
11 Correct 192 ms 800 KB Output is correct
12 Execution timed out 2049 ms 1200 KB Time limit exceeded
13 Halted 0 ms 0 KB -