Submission #62219

#	Time	Username	Problem	Language	Result	Execution time	Memory
62219		kingpig9	Match (CEOI16_match)	C++11	37 / 100	2049 ms	1200 KiB

match

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 63