oj.uz

Submission #52899

# Submission time Handle Problem Language Result Execution time Memory
52899 2018-06-27T06:54:47 Z Petr(#1971) Match (CEOI16_match) C++11
37 / 100
 3 ms 688 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n;
char s[100010];
char ans[100010];

bool solve(int l, int r){
	if(l>r) return 1;
	if(s[r] == s[l]){
		if(solve(l+1, r-1)){
			ans[l]='('; ans[r]=')';
			return 1;
		}
	}
	stack<char> stk;
	for(int i=r; l<=i; --i){
		if(stk.empty() || stk.top() != s[i]) stk.push(s[i]);
		else {
			stk.pop();
			if(stk.empty()){
				if(l<i-1 && s[l]==s[i-1]){
					if(solve(l+1, i-2) && solve(i, r)){
						ans[l]='('; ans[i-1]=')';
						return 1;
					}
				}
			}
		}
	}
	return 0;
}

int main()
{
	scanf("%s", s+1);
	n = strlen(s+1);
	n = min(n, 2000);
	
	if(n&1){ puts("-1"); return 0; }
	
	if(solve(1, n)){
		puts(ans + 1);
	} else puts("-1");
	
	return 0;
}

Compilation message

match.cpp: In function 'void read(int&)':
match.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
match.cpp: In function 'void read(ll&)':
match.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~
match.cpp: In function 'int main()':
match.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s+1);
  ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 688 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Incorrect 3 ms 688 KB Output isn't correct
9 Halted 0 ms 0 KB -