# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
127756 | sealnot123 | Match (CEOI16_match) | C++14 | 19 ms | 11724 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define push_back pb
#define emplace_back eb
using namespace std;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 100007;
int dp[N][26];
char str[N], ans[N];
stack<char> sta;
int n;
void play(int l, int r){
if(l>r) return ;
ans[l] = '(';
int a = dp[r][str[l]-'a'];
ans[a] = ')';
play(l+1, a-1); play(a+1, r);
}
int main(){
int a,b,c,d,i,j,k,l;
scanf("%s",str+1);
n = strlen(str+1);
for(i=1;i<=n;i++){
dp[i][str[i]-'a'] = i;
a = dp[i-1][str[i]-'a'];
if(!a) continue;
for(j=0;j<26;j++) dp[i][j] = max(dp[i][j], dp[a-1][j]);
}
// check
for(i=1;i<=n;i++){
if(!sta.empty() && sta.top() == str[i]) sta.pop();
else sta.push(str[i]);
}
if(!sta.empty()){
printf("-1");
return 0;
}
// do ans
play(1, n);
printf("%s",ans+1);
return 0;
}
/*
abbccddabbccdd
abbacabbac
accaccacca
aaaabbbb
aaabcaacba (()((())))
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |