Codeforces Round #282 (Div. 2) Treasure

原題連結：

http://codeforces.com/contest/495/problem/C

C. 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.

題意：一串字元串隻含有'(',')','#',三種字元，你需要把其中的每個‘#’變為一個或者多個')'，使字元串滿足兩個條件，①整個字元串‘（’與‘）’數量相等，②任意位置i，在它和它之前的'）'數不能超過‘（’數。如果無解輸出-1，否則每行輸出從前往後每個‘#’所替換的‘）’量。 思路：由于并不要求任意位置都（）配對，是以可以把最後 一個‘#‘之前的’#‘都全部設定為1，隻需要考慮最後一個’#‘是否滿足條件即可。 方法：①首先保證每個‘#’至少替換一個‘）’，方法是，讀入按單個字元讀入，讀入‘#’時，存儲字元串增加’）‘’#’兩個字元，并記錄最後一個’#‘的位置last。②從開頭往last掃，計算截止i一共多出多少個’（‘，記錄為nl，若任意位置nl<0了，說明’）‘多于‘（’，而由于我們之前每個‘#’隻置換一個‘）’，‘）’是最小值，則說明條件已經不滿足。③從尾部往last掃，判斷last之後是否出現不合理，這時候，同樣記錄‘（’的數量nr，如果任意位置nr>0，說明從i~n（總長度）中‘（’多于‘）’，相對應從1~i-1，就一定有‘（’多于‘）’，不滿足條件。④從last掃往尾部，判斷條件如①，但是此時正式的‘（’多出數量為nl+nr； 這道題應該有很簡單的方法，但是太挫隻會這個方法，還好資料量小。。。

#include "stdio.h"
#include "string.h"

int main()
{
	int n=0,nl=0,nr=0,ans[100010],nj=0,flag=1,last;
	char a[200010],in;
	memset(ans,0,sizeof(ans));
    while(1)
	{
		in=getchar();
		if(in=='\n')
		{
			break;
		}
		if(in=='#')
		{
			a[++n]=')';
			a[++n]='#';
			last=n;
		}
		else
			a[++n]=in;
	}
	for(int i=1;i<last;i++)
	{
		if(a[i]=='(')
		{
			nl++;
		}
		else if(a[i]==')')
		{
			nl--;
		}
		if(nl<0)
		{
			flag=0;
			break;
		}
	}
	if(flag)
	{
		for(int i=n;i>=last+1;i--)
		{
			if(a[i]=='(')
				nr++;
			else if(a[i]==')')
				nr--;
			if(nr>0)
			{
				flag=0;
				break;
			}
		}
	}
	nr=0;
	if(flag)
	{
		for(int i=last+1;i<=n;i++)
		{
			if(a[i]=='(')
				nr++;
			else if(a[i]==')')
				nr--;
			if(nl+nr<0)
			{
				flag=0;
				break;
			}
		}
	}
	if(flag)
	{
		for(int i=0;i<last;i++)
		{
			if(a[i]=='#')
				printf("1\n");
		}
		printf("%d\n",nl+nr+1);
	}
	else
	{
		printf("-1\n");
	}
	return 0;
}