oj.uz

Submission #52887

# Submission time Handle Problem Language Result Execution time Memory
52887 2018-06-27T06:31:52 Z Petr(#1971) Match (CEOI16_match) C++11
10 / 100
 2000 ms 508 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 even(int l, int r){
	int cnt[26];
	for(int i=0; i<26; ++i) cnt[i]=0;
	for(;l<=r;++l) ++cnt[s[l]-'a'];
	for(r=0; r<26; ++r) if(cnt[r]&1) return 0;
	return 1;
}

bool solve(int l, int r){
	if(l > r) return 1;
	for(int i=r; l<i; --i){
		if(s[i]==s[l] && even(l+1, i-1) && even(i+1, r)){
			ans[l] = '(';
			ans[i] = ')';
			if(solve(l+1, i-1) && solve(i+1, r)) return 1;
		}
	}
	return 0;
}

int main()
{
	scanf("%s", s+1);
	n = strlen(s+1);
	n = min(n, 2000);
	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:42: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 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Execution timed out 2065 ms 508 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Execution timed out 2065 ms 508 KB Time limit exceeded
5 Halted 0 ms 0 KB -