Submission #198205

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
198205	2020-01-25T06:27:54 Z	ruler	Match (CEOI16_match)	C++14	37 / 100	2000 ms	504 KB

match

// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////

const int N = 1e4 + 5;

string S;
int n;

bool F(stack<char> st, int pos) {
	for (int i = pos; i < n; i++) {
		if (st.empty() || st.top() != S[i]) st.push(S[i]);
		else st.pop();
	}
	return st.empty();
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> S; n = sz(S);
	stack<char> st;
	string ans = "";
	for (int i = 0; i < n; i++) {
		st.push(S[i]);
		if (!F(st, i + 1)) {
			st.pop();
			if (st.empty() || st.top() != S[i]) die(-1);
			st.pop();
			ans += ')';
		} else ans += '(';
	}
	cout << ans << endl;

	return 0;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	6 ms	376 KB	Output is correct
7	Correct	8 ms	376 KB	Output is correct

Subtask #3

0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	6 ms	376 KB	Output is correct
7	Correct	8 ms	376 KB	Output is correct
8	Correct	113 ms	504 KB	Output is correct
9	Correct	135 ms	504 KB	Output is correct
10	Correct	93 ms	440 KB	Output is correct
11	Correct	78 ms	376 KB	Output is correct
12	Execution timed out	2056 ms	504 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-