#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];
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;
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;
return "-";
}
}
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;
}
return '('+s1+')'+s2;
}
//cout << *it << " " << from << endl;
return "-";
}
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']++;
}
cout << solve(0,n-1);
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
452 KB |
Output is correct |
3 |
Incorrect |
2 ms |
452 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
452 KB |
Output is correct |
3 |
Incorrect |
2 ms |
452 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
452 KB |
Output is correct |
3 |
Incorrect |
2 ms |
452 KB |
Output isn't correct |