oj.uz

Submission #63066

# Submission time Handle Problem Language Result Execution time Memory
63066 2018-07-31T15:00:44 Z bazsi700 Match (CEOI16_match) C++14
37 / 100
 400 ms 253100 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL

//13:45

int cnt[2005][26];
bool was[2005][2005];
string dp[2005][2005];
vector<set<int> > occ(26);
string s;
int n;

string solve(int from, int to) {
	if(from > to) {
		return "";
	}
	if((to-from)%2 == 0) {
		return "-";
	}
//	cout << from << " " << to << endl;
	if(was[from][to]) {
		return dp[from][to];
	}
	was[from][to] = true;
	for(int i = 0; i < 26; i++) {
		if((cnt[to][i]-(from == 0 ? 0 : cnt[from-1][i]))%2) {
		//	cout << cnt[to][i] << endl;
		//	cout << i << endl;
			dp[from][to] = "-";
			return dp[from][to];
		}
	}
	int star = s.at(from)-'a';
	auto it = occ[star].upper_bound(to);
	it--;
	while(*it > from) {
		//cout << *it << " " << from << endl;
		string s1 = solve(from+1,*it-1);
		if(s1.length() == 1) {
			it--;
			continue;
		}
		string s2 = solve(*it+1,to);
		if(s2.length() == 1) {
			it--;
			continue;
		}
		dp[from][to] = '('+s1+')'+s2;
		return dp[from][to];
	}
	//cout << *it << " " << from << endl;
	dp[from][to] = "-";
	return dp[from][to];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	n = s.length();
	for(int i = 0; i < n; i++) {
		if(i != 0) {
			for(int j = 0; j < 26; j++) {
				cnt[i][j] = cnt[i-1][j];
			}
		}
		occ[s.at(i)-'a'].insert(i);
		cnt[i][s.at(i)-'a']++;
	}
	string ans =solve(0,n-1);
	if(ans.length() == 1) {
		cout << -1;
	} else {
		cout << ans;
	}
	//cout << solve(0,n-1) << endl;
	return 0;
	if(n > 18) {
		return 0;
	}
	string str = "-1";
	for(int mask = 0; mask < (1<<n); mask++) {
		stack<int> st;
		bool good = true;
		string currstr = "";
		for(int i = 0; i < n; i++) {
			if(mask&(1<<i)) {
				st.push(i);
				currstr+= '(';
			} else {
				currstr+= ')';
				if(st.empty()) {
					good = false;
					break;
				}
				if(s.at(st.top()) != s.at(i)) {
					good = false;
					break;
				}
				st.pop();
			}
		}
		if(!st.empty()) {
			good = false;
		}
		if(good) {
			if(str.at(0) == '-' || str > currstr) {
				str = currstr;
			}
		}
	}
	cout << str;
	vector<int> cnt2(260,0);
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 126200 KB Output is correct
2 Correct 115 ms 126340 KB Output is correct
3 Correct 117 ms 126340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 126200 KB Output is correct
2 Correct 115 ms 126340 KB Output is correct
3 Correct 117 ms 126340 KB Output is correct
4 Correct 146 ms 128132 KB Output is correct
5 Correct 145 ms 128132 KB Output is correct
6 Correct 126 ms 129592 KB Output is correct
7 Correct 325 ms 130804 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 126200 KB Output is correct
2 Correct 115 ms 126340 KB Output is correct
3 Correct 117 ms 126340 KB Output is correct
4 Correct 146 ms 128132 KB Output is correct
5 Correct 145 ms 128132 KB Output is correct
6 Correct 126 ms 129592 KB Output is correct
7 Correct 325 ms 130804 KB Output is correct
8 Runtime error 400 ms 253100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -