QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398417 | #5534. Match | sichengzhou | 0 | 1ms | 3908kb | C++14 | 1.5kb | 2024-04-25 11:51:36 | 2024-04-25 11:51:37 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
char ch[N];
int f[N][26],fa[N];
int stk[N],tp;
int vis[N];
int main()
{
scanf("%s",ch+1);n=strlen(ch+1);
for(int i=1;i<=n;i++)
{
if(tp>=1&&stk[tp]==ch[i]-'a')
{
tp--;
}else{
stk[++tp]=ch[i]-'a';
}
}
if(tp)
{
printf("-1");
return 0;
}
fa[n]=0;
for(int i=n-1;i>=1;i--)
{
int x=i+1;
while(1)
{
if(ch[i]==ch[x])
{
fa[i]=x+1;break;
}else{
if(fa[x]>n||fa[x]==0)
{
fa[i]=0;
break;
}
x=fa[x];
}
}
// cout<<i<<' '<<fa[i]<<endl;
}
for(int i=n+1;i>=1;i--)
{
if(fa[i]==0)
{
continue;
}
for(int j=0;j<26;j++)
{
f[i][j]=f[fa[i]][j];
}
f[i][ch[fa[i]-1]-'a']=max(fa[i]-1,f[i][ch[fa[i]-1]-'a']);
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
int x=f[i][ch[i]-'a'];
vis[i]=1;
vis[x]=2;
}
}
for(int i=1;i<=n;i++)
{
if(vis[i]==1)
{
printf("(");
}else if(vis[i]==2){
printf(")");
}else{
printf("*");
}
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 1ms
memory: 3836kb
input:
abbaaa
output:
(()())
result:
ok single line: '(()())'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3908kb
input:
cbbbbccbbccbbbbbbc
output:
(((((((((()(((()))
result:
wrong answer 1st lines differ - expected: '(((((((()))())))))', found: '(((((((((()(((()))'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%