oj.uz

Submission #52891

# Submission time Handle Problem Language Result Execution time Memory
52891 2018-06-27T06:38:47 Z Petr(#1971) Match (CEOI16_match) C++11
10 / 100
 6 ms 3244 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];

int al[100010][26];

bool even(int l, int r){
	for(int i=0; i<26; ++i) if((al[r][i]+al[l-1][i])&1) return 0;
	return 1;
}

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

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

int main()
{
	scanf("%s", s+1);
	n = strlen(s+1);
	n = min(n, 2000);
	
	for(int i=1; i<=n; ++i){
		copy(al[i-1], al[i-1]+26, al[i]);
		++al[i][s[i]-'a'];
	}
	
	if(solve(1, n)){
		make(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:57: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 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Incorrect 6 ms 3244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Incorrect 6 ms 3244 KB Output isn't correct
5 Halted 0 ms 0 KB -