QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #37390 | #1194. Parehtneses Editor | claes | WA | 8ms | 8036kb | C++ | 1.3kb | 2022-07-01 12:45:04 | 2022-07-01 12:45:07 |
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)
{
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("KKK %d %d %d\n",suma[p-1]-suma[r],sumb[p-1]-sumb[r],pre[p-1]);
// printf("%d\n",flag);
pre[p]=pre[r-1]+1;ans[p]+=pre[p];
}
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]);
}
// printf("len=%d %d\n",len,Q[len]);
// putchar('q');
// for(int k=1;k<=cnt;k++) printf(" %d",q[k]);
// puts("");
}
return 0;
}
/*
))(((-)(()((---(-)(-())-(()()(-)--(()))
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7844kb
input:
(()())---)
output:
0 0 1 1 3 4 3 1 1 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 7860kb
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: 8ms
memory: 8036kb
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 9 12 9 7 7 9 9 9 9 10 11 10 11 11 11 12 12 12 13 15 15 15 15 18 20 23 25 25 25 25 25 25 25 26 26 26 26 27 27 29 29 32 32 36 37 39 37 37 37 38 40 40 40 40 40 40 40 41 44 41 41 43 46 43 46 46 46 46 46 43 46 48 49 50 50 50 50 ...
result:
wrong answer 1214th numbers differ - expected: '773', found: '774'