QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#37362 | #1194. Parehtneses Editor | claes | WA | 7ms | 7856kb | C++ | 1.2kb | 2022-07-01 11:25:21 | 2022-07-01 11:25:23 |
Judging History
answer
//Leo
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 200200
using namespace std;
int cnt,len,q[N],Q[N],op[N];
int ans[N],suma[N],sumb[N],pre[N];
char st[N];
void solve(int i,int p)
{
bool flag=false;
int r=q[cnt--];
// printf("%d ",r);
op[i]=r;
if(suma[p-1]-suma[r] == sumb[p-1]-sumb[r])
if(suma[p-1]-suma[r] == pre[p-1]) flag=true;
// printf("%d\n",flag);
if(flag){pre[p]=pre[r-1]+1;ans[p]+=pre[p];}
else pre[p]=0;
}
int main()
{
scanf("%s",st);
Q[0]=0;
if(st[0]=='(') q[++cnt]=0,suma[0]=1;
else sumb[0]=1;
ans[0]=0;
puts("0");
for(int i=1,j=1;i<strlen(st);i++,j++){
ans[j]=ans[j-1];
suma[j]=suma[j-1];
sumb[j]=sumb[j-1];
if(st[i]=='('){
q[++cnt]=j;
suma[j]++;
pre[j]=0;
Q[++len]=i;
printf("%d\n",ans[j]);
}
else if(st[i]==')'){
sumb[j]++;
if(cnt) solve(i,j);
else pre[j]=0;
Q[++len]=i;
printf("%d\n",ans[j]);
}
else{
j--;
if(st[Q[len]]==')') q[++cnt]=op[Q[len]];
else cnt--;
len--;
printf("%d\n",ans[--j]);
}
// putchar('q');
// for(int k=1;k<=cnt;k++) printf(" %d",q[k]);
// puts("");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7856kb
input:
(()())---)
output:
0 0 1 1 3 4 3 1 1 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 7848kb
input:
()--()()----)(()()))
output:
0 1 0 0 0 1 1 3 1 1 0 0 0 0 0 1 1 3 4 4
result:
ok 20 numbers
Test #3:
score: -100
Wrong Answer
time: 7ms
memory: 5924kb
input:
))(((-)(()((---(-)(-())-(()()(-)--(())))--()((())-)(()(())((-))))(-(((()((()()()()))-(())((((--))-())-)(-(--))))((((-)(-(-)((((()--(---)(-))()(-)(()()-(())()(()()((()()))))(()(()(-(--)-()((()(((()-))-)(()-()()-(-((-)(-)(((()-)))))-())()-(()((()(-)()))((-))())))()()()(-(-(())-()(()-)-))((()))((--(-()...
output:
0 0 0 0 0 0 1 1 1 2 2 2 2 2 1 1 1 2 2 2 2 4 6 4 4 4 5 5 7 7 7 10 7 5 5 5 6 7 7 7 7 7 7 9 9 9 9 10 11 10 11 11 11 12 12 12 13 15 15 15 15 18 18 18 18 18 18 18 18 18 18 19 19 19 19 20 20 22 22 25 25 29 30 30 30 30 30 31 33 33 33 33 33 33 33 34 37 34 34 36 39 36 39 39 39 39 39 36 39 39 39 39 39 39 39 3...
result:
wrong answer 39th numbers differ - expected: '9', found: '7'