QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#37362#1194. Parehtneses EditorclaesWA 7ms7856kbC++1.2kb2022-07-01 11:25:212022-07-01 11:25:23

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-01 11:25:23]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:7856kb
  • [2022-07-01 11:25:21]
  • 提交

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'