QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#355126	#5108. Prehistoric Programs	ucup-team052^#	WA	14ms	36388kb	C++23	1.1kb	2024-03-16 13:40:26	2024-03-16 13:40:27

Judging History

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

[2024-03-16 13:40:27]
评测

测评结果：WA
用时：14ms
内存：36388kb

查看

[2024-03-16 13:40:26]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
string s[N];
int mn[N],sum[N],id[N],vis[N];
int n;
signed main()
{
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++)
	{
		int l=s[i].length();
		int cur=0;
		for(int j=0;j<l;j++)
		{
			if(s[i][j]=='(') cur++;
			else cur--;
			mn[i]=min(mn[i],cur);
		}
		sum[i]=cur;
		id[i]=i;
	}
// 	for(int i=1;i<=n;i++) printf("%d %d\n",mn[i],sum[i]);
	sort(id+1,id+n+1,[&](int x,int y){return mn[x]>mn[y];});
	vector<int> ans;
	int cur=0;
	for(int i=1;i<=n;i++)
	{
		int u=id[i];
		if(mn[u]+cur>=0&&sum[u]>=0)
		{
			vis[u]=1,ans.push_back(u);
			cur+=sum[u];
		}
	}
	sort(id+1,id+n+1,[&](int x,int y){return -sum[x]-mn[x]>-sum[y]-mn[y];});
	for(int i=1;i<=n;i++)
	{
		int u=id[i];
		if(!vis[u]&&mn[u]+cur>=0)
		{
			cur+=sum[u];
			ans.push_back(u);
			vis[u]=1;
		}
	}
	if((int)ans.size()!=n) printf("impossible\n");
	else
	{
		for(int i:ans) printf("%d\n",i);
	}
	return 0;
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 14ms

memory: 36388kb

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

result:

ok good plan

Test #2:

score: 0

Accepted

time: 7ms

memory: 35156kb

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

result:

ok good plan

Test #3:

score: 0

Accepted

time: 7ms

memory: 35028kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

score: 0

Accepted

time: 3ms

memory: 34956kb

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: 0

Accepted

time: 3ms

memory: 35120kb

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

score: 0

Accepted

time: 9ms

memory: 35060kb

input:

3
()
(
)

output:

1
2
3

result:

ok good plan

Test #7:

score: 0

Accepted

time: 4ms

memory: 34992kb

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

score: 0

Accepted

time: 7ms

memory: 34956kb

input:

5
))(
(()
)(
(
)

output:

result:

ok good plan

Test #9:

score: 0

Accepted

time: 7ms

memory: 35248kb

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

score: 0

Accepted

time: 0ms

memory: 35160kb

input:

6
)
()
()()()
((
)
)

output:

impossible

result:

ok impossible

Test #11:

score: 0

Accepted

time: 0ms

memory: 35040kb

input:

500
(
)
)
(
)(
(
(
)
))(
(
(
(
(
)
)
(
(
)
(
(
)
(
()(()
(
)())
(
(
)
(
)()((
(
)
(
)
)
(
(
(
)
(
(
)
)
)(
(
(
)
)
(
)
(
(
(
)
(
(
())))
(
(
(
)
(
)
)
(
(
)
)
(
(
(
(
(
()
(
(
(
(
(
((
)
(
(
)
(
(
(
)
())
(
(
(
)
(
(
(
)
)
(
)
)
(
)
(
(
(
(
)
(
)
)
)
)
(
)
)))()(
(
)
)
(
)
)(
)
(
)
)
))
(
(
(
(
(
(
...

output:

result:

ok good plan

Test #12:

score: 0

Accepted

time: 0ms

memory: 35216kb

input:

50
)
)
((((()())())))(())(())
()(((()))
(((()))(()
()(((
))
)
)()))(()(()())(((((()
(
)
)
)((
)()((
())()))
(())))()
(((
))))(()
()(())(()))())()
)
)
(
(
(
(
((())()())())))(((())
()(
(()(())()((()
()(((()())))())()(
)
)((()
(
)
((
)
()(
(
(
)
)))((())
)
()))()(((()(()
((
((()))(())(()())(()())())()...

output:

result:

ok good plan

Test #13:

score: 0

Accepted

time: 7ms

memory: 35288kb

input:

50
)
(
)()(
())(
()()(((((())(
)(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...

output:

result:

ok good plan

Test #14:

score: 0

Accepted

time: 10ms

memory: 35756kb

input:

150
))(()))(())(())))()))())()()()(())(((())))()))))()
)))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...

output:

result:

ok good plan

Test #15:

score: 0

Accepted

time: 3ms

memory: 36164kb

input:

150
)))(
(()
(())((())))(()))()(()
((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()())))))
(
...

output:

result:

ok good plan

Test #16:

score: 0

Accepted

time: 3ms

memory: 35644kb

input:

150
)()((
)
)))())))
)()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(())
()()
)
(())()))(())(()((())()()())())((...

output:

result:

ok good plan

Test #17:

score: 0

Accepted

time: 4ms

memory: 35336kb

input:

750
(()()((()((((())()((()))()()))()))(()()(()))(()(())()))((((((
)))))))
)
((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()(
)
)
(
)()(((()(())))()))))(((((((()))()()()(()())))(()())(()((
(
)
)(()))
((())(...

output:

result:

ok good plan

Test #18:

score: 0

Accepted

time: 3ms

memory: 35432kb

input:

100
)
)
)
(
)
(
))))()
)
(
(
(
(
)
)
)
)
(
(
(
(
())
(
)
)
)((
)
(
(
(
)
(
(
)
)
)
)
()((
(
)
)
)
)(((
((((
(
)
(
)
((
)
(
(
)
(
())(()))
)
)
(
)
(
(
(
(
)))()()
)
(
(
(
(
)
(
)
)
)
(
)
)
)
)
(
)
(
(
)
(
)
(
(
(
)
)
(
)
)
(
)((((
)
)
()((()()(()))))
)
(

output:

result:

ok good plan

Test #19:

score: -100

Wrong Answer

time: 3ms

memory: 36020kb

input:

100
)
()(
(
)
(
)
(
(
)
)
)(()
)
)))
)
)
(
(
(
)
(
(
)
(
)
(
(
(
))(
(
(
))((
(
)
(
))())
)
(()
)
)
(
)
(
(
)
)
(
)
(
))
(
(
)
)
(
)
)
)
)
(
())
)
(
(
)
)
(
)
(
))
(
)
)
(
(
(((
(
(
(()
)
)()())(()((()((())
(
)
)
(
(
)
)
(
)
(
)
(
))(
)
(
(
(
)
(
(((())

output:

result:

wrong answer wrong plan (expected impossible)