cf494A Treasure

A. Treasure
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output

Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string s written on the door consisting of characters '(', ')' and '#'. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each '#' with one or more ')' characters so that the final string becomes beautiful.

Below there was also written that a string is called beautiful if for each i (1 ≤ i ≤ |s|) there are no more ')' characters than '(' characters among the first i characters of s and also the total number of '(' characters is equal to the total number of ')' characters.

Help Malek open the door by telling him for each '#' character how many ')' characters he must replace it with.

Input

The first line of the input contains a string s (1 ≤ |s| ≤ 105). Each character of this string is one of the characters '(', ')' or '#'. It is guaranteed that s contains at least one '#' character.

Output

If there is no way of replacing '#' characters which leads to a beautiful string print  - 1. Otherwise for each character '#' print a separate line containing a positive integer, the number of ')' characters this character must be replaced with.

If there are several possible answers, you may output any of them.

Sample test(s)
input
(((#)((#)
output
1
2
input
()((#((#(#()
output
2
2
1
input
#
output
-1
input
(#)
output
-1
Note

|s| denotes the length of the string s.

题意是要把#替换成1个以上的")",使得"("和“)”的个数相等,且对于s的任意一个前缀,“)“的个数不大于”)“的个数。

因为个数相等,所以分配给#的”)“的个数之和是确定的。

然后很显然的贪心是前k-1个#都只分配一个")",最后一个#多分配一点")"使”(“和”)"的个数相等就好了

于是变成模拟题了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
inline LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void write(LL a)
{
if (a<0){printf("-");a=-a;}
if (a>=10)write(a/10);
putchar(a%10+'0');
}
char ch[100010];
int a[100010];
int s[100010];
int len,x,y,z,lst;
int main()
{
scanf("%s",ch);
for (int i=1;ch[i-1];i++)
{
if (ch[i-1]=='(')a[i]=1,x++;
if (ch[i-1]==')')a[i]=-1,y++;
if (ch[i-1]=='#')a[i]=0,z++,lst=i;
len=i;
}
if (x-y<z)
{
printf("-1");
return 0;
}
for (int i=1;i<=len;i++)
{
s[i]=s[i-1];
if (a[i]!=0)s[i]+=a[i];
else if (i==lst)s[i]-=x-(y+z-1);
else s[i]--;
if (s[i]<0)
{
printf("-1");
return 0;
}
}
for (int i=1;i<z;i++)
printf("1\n");
printf("%d\n",x-y-(z-1));
}
上一篇:mysql最大连接数


下一篇:反编译sencha toucha打包的apk文件,修改应用名称支持中文以及去除应用标题栏