QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#591620 | #5534. Match | ifffer_2137 | 37 | 1543ms | 153300kb | C++14 | 1.9kb | 2024-09-26 16:49:30 | 2024-09-26 16:49:30 |
Judging History
answer
//From: ifffer_2137
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define eb emplace_back
#define pii pair<int,int>
#define mkpr make_pair
#define fir first
#define sec second
inline int read(){
char ch=getchar();int x=0,w=1;
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
const int maxn=2e3+5;
const int maxm=1e5+5;
int n;
string s;
string dp[maxn][maxn];
int stk[maxm],tp;
int ch[maxm];
char ans[maxm];
signed main(){
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("test.out","w",stdout);
#endif
cin.tie(0),cout.tie(0);
cin>>s;n=s.size();s=' '+s;
if(n<=2000){
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]="0";
for(int i=2;i<=n;i++){
for(int l=1;l+i-1<=n;l++){
int r=i+l-1;
if(s[l]==s[r]){
if(l+1<r&&dp[l+1][r-1]!="0") dp[l][r]=min(dp[l][r],'('+dp[l+1][r-1]+')');
else if(l+1==r) dp[l][r]=min(dp[l][r],(string){"()"});
}
for(int j=l;j<r;j++){
if(dp[l][j]=="0"||dp[j+1][r]=="0") continue;
dp[l][r]=min(dp[l][r],dp[l][j]+dp[j+1][r]);
}
}
}
if(dp[1][n]=="0") puts("-1");
else cout<<dp[1][n]<<"\n";
return 0;
}
for(int i=1;i<=n;i++){
if(tp&&s[stk[tp]]==s[i]) ans[stk[tp]]='(',ans[i]=')',ch[stk[tp]]=i,ch[i]=stk[tp],tp--;
else stk[++tp]=i;
}
if(tp){
puts("-1");
return 0;
}
while(1.0*clock()/CLOCKS_PER_SEC<0.9){
for(int i=n;i>=1;i--){
if(ch[i]>i) continue;
tp=0;int pos=0;
for(int j=i;j<n;j++){
if(j>i){
if(ans[j]==')'&&tp&&ans[stk[tp]]=='(') tp--;
else stk[++tp]=j;
}
if(tp) continue;
if(s[j+1]==s[i]&&ch[j+1]>j+1) pos=j+1;
}
if(pos){
ch[ch[i]]=ch[pos],ch[ch[pos]]=ch[i];
ch[i]=pos,ch[pos]=i;
ans[i]='(',ans[pos]=')';
}
}
}
for(int i=1;i<=n;i++) cout<<ans[i];
cout<<"\n";
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 12ms
memory: 129488kb
input:
abbaaa
output:
(()())
result:
ok single line: '(()())'
Test #2:
score: 10
Accepted
time: 15ms
memory: 129500kb
input:
cbbbbccbbccbbbbbbc
output:
(((((((()))())))))
result:
ok single line: '(((((((()))())))))'
Test #3:
score: 10
Accepted
time: 12ms
memory: 129228kb
input:
ddbcbdacccbddaba
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 27
Accepted
Dependency #1:
100%
Accepted
Test #4:
score: 27
Accepted
time: 191ms
memory: 129480kb
input:
fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...
output:
((((((())))(()))(((()(((()((((()(()))))((((((()((((())(())((((((((())))(()))()))((((((()((()(((()))))(())))((((((())))(((((((()())(((((())())(()()((()(((((((((()))()))(()())))()())())(()(()))))(()))))()))(((())(())))())())())))))())(()())))(())()))))))((())())))))))))(()))))())((())()))(())))((())((...
result:
ok single line: '((((((())))(()))(((()(((()((((...))(())(()))(())())))))))((())))'
Test #5:
score: 27
Accepted
time: 235ms
memory: 129560kb
input:
vvrookjqmmooqlfhnnhflrcbxuuxftajjcqdppoowsswniwsswzzvvisqqbxqniinqeeeaanojvhhttviezzxujjuxyyektlltkoouwwukcqqcifommxxorrnnfgzzyggygvzzvgtxqqxkkummpssllpubbssuubddbebttkkblzzofmmyooyfoqqlpnzznppmvbnnlrrqqlwwbeiievxcnnwppweasjhcchjcarobbogljjlqqgznffmlfabjpiipepummubbbbggzzpjjvvejvgmmqrrkffkqgefrrdbbd...
output:
()(()(((()())(((())))((((())(((()(((((()(())(((())()())(()((((()))(()()((((()(((((()((()))())((())(()(()))(())(((()())()())(()(())((()))((())()(()(()())(()()))(())((()())(()((()(())))())((())()(((()(()())())(()))((()(())(((((()))((((())((())()(((()(((((((())(((())(())()())()()))((()(()(())))((()(())...
result:
ok single line: '()(()(((()())(((())))((((())((...()(()(()))))(())()))(()()()))))'
Test #6:
score: 27
Accepted
time: 921ms
memory: 153300kb
input:
uuueeeuuueeueeeeeeeuueueueeuuuuueeeueeeeeueueueuueuueeueuuuuuuueueueeuueeueeuueeueuueeeueuueeeueueueuueuuueeeeueuuuuueuueueueuuueuuueeeeuueeueeeeeuuuueeeeeuuuueeuuuueueeueuueuuueeeeuueueueueeeeeeeuueueuuueuuuueueeuuueuuuueuuueeuueeeeueeuueuuuuuuuuueeeueuuueueeueeeeuueeuuuueuueeuuueuueeuuueeueeuueueu...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...
result:
ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'
Test #7:
score: 27
Accepted
time: 1543ms
memory: 131952kb
input:
qeeqqqeeqqqquqeeeequuquuuqqqeqqqeeqquqqeeeuuueqqeeqqqqqeeeeeeeeeuqeqquuueeuqeqeqqueeuuuueeeeuuuqqquueuqeeeqeeeqeeqeqqequeeueqquuquqququqqqqueuqueuuuueuueeuueueeququeeeqeeqeeqqeuqeuequququuuuuueuuueeeuueeeqeuqquueuueeuquuqqqeqeuqqeqqquuueuuuuueeuuqeeeeeeeueuuuququeqqqqeeuqeuuquuueueeuuuqeqeeuqqqquuuq...
output:
((((((()()))((((()(((((()(()((((()))((((()((((((()(()))((((())))((((((()()))(((((((((())()))())(()()(((((((((((((((()))(()((((())(()))((()))))((((((((((())))(()((((((((())))())(((((((((((((())((()(((()(((((((((((((())(()(((((((()(((((((((((((()()(((((((((((()((((((((((((((()((((((()())(((()((())(()(...
result:
ok single line: '((((((()()))((((()(((((()(()((...))))((())))())))((())))))()))))'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #8:
score: 0
Wrong Answer
time: 889ms
memory: 129460kb
input:
jggeedfjvfppgdgqqufesgeljdjjoqqsgprqdddgueugpodpfldvgdgdpeuljfqrdrlgljugdujjdjrjevlqlqufoosjvsqvqgvruqrgsfsquqoovvvvfpofjdpvuesrqdfegguggrlvslsqjpddorjlodqflspgopeuppeoleeojlvjpddopjsouregflrfgpgqvlquqpplgrudllvdfsrplfljupveleggedljopqjjolslfpeeluvsufofpdlodgdvfvsujlgjpvggduorfforllorgsgrppvegglgver...
output:
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()((((((((((((((((())((((((((((((((()((((((((((((((((((((((((((((((((((((((((((((()(((((((((...
result:
wrong answer 1st lines differ - expected: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))', found: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'