oj.uz

Submission #52903

# Submission time Handle Problem Language Result Execution time Memory
52903 2018-06-27T07:02:00 Z Petr(#1971) Match (CEOI16_match) C++11
0 / 100
 2000 ms 655360 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 stk[1000010], top;

map<pp,int> cache;

bool solve(int l, int r){
	if(l>r) return 1;
	pp key{l, r};
	auto it = cache.find(key);
	if(it!=cache.end()) return it->second > 0;
	if(s[r] == s[l]){
		if(solve(l+1, r-1)){
			return cache[key]=r;
		}
	}
	int top_base = top;
	for(int i=r; l<=i; --i){
		if(top == top_base || stk[top-1] != s[i]) stk[top++] = s[i];
		else {
			--top;
			if(top == top_base){
				if(l<i-1 && s[l]==s[i-1]){
					if(solve(l+1, i-2) && solve(i, r)){
						top = top_base;
						return cache[key]=i-1;
					}
				}
			}
		}
	}
	return cache[key]=-1;
}

void make(int l, int r){
	if(l>r) return;
	pp key{l, r};
	auto it = cache.find(key);
	ans[l] = '('; ans[it->second] = ')';
	make(l+1, it->second-1);
	make(it->second+1, r);
}

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)){
		make(1, n);
		puts(ans + 1);
	} else puts("-1");
	
	return 0;
}

Compilation message

match.cpp: In function 'bool solve(int, int)':
match.cpp:31:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    return cache[key]=r;
match.cpp:43:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
       return cache[key]=i-1;
match.cpp:49:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return cache[key]=-1;
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:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s+1);
  ~~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Execution timed out 2093 ms 655360 KB Time limit exceeded

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Execution timed out 2093 ms 655360 KB Time limit exceeded

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Execution timed out 2093 ms 655360 KB Time limit exceeded