oj.uz

Submission #49063

# Submission time Handle Problem Language Result Execution time Memory
49063 2018-05-21T14:57:08 Z Namnamseo Match (CEOI16_match) C++17
0 / 100
 2000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

char Data[100010];
char ans [100010];
int nxt[18][100010];
deque<char> Q[18][100010];
int n;
stack<char> s;

deque<char> merge(deque<char>& a, deque<char>& b){
	deque<char> s;
	for(char x:a){
		if(s.size() && s.back()==x) s.pop_back();
		else s.pb(x);
	}
	for(char x:b){
		if(s.size() && s.back()==x) s.pop_back();
		else s.pb(x);
	}
	return s;
}

int main(){
	freopen("match.in", "r", stdin);
	//freopen("match.out", "w", stdout);
	scanf("%s", Data);
	n=strlen(Data);

	for(int i=0; i<n; ++i){
		Q[0][i].pb(Data[i]);
		nxt[0][i]=i+1;
	}
	nxt[0][n-1]=-1;

	for(int i=1; i<18; ++i){
		for(int j=0; j<n; ++j){
			nxt[i][j]=nxt[i-1][nxt[i-1][j]];
			Q[i][j]=merge(Q[i-1][j], Q[i-1][nxt[i-1][j]]);
		}
	}

	deque<char> cur;
	for(int i=0; i<n; ++i){
		deque<char> tiny;
		tiny.pb(Data[i]);
		auto tmp=merge(cur, tiny);
		int p=i;
		for(int j=17; 0<=j; --j){
			if(nxt[j][p]!=-1){
				tmp=merge(tmp, Q[j][p]);
				p=nxt[j][p];
			}
		}
		if(tmp.size() == 0u){
			ans[i]='(';
		} else {
			ans[i]=')';
		}
		cur = merge(cur, tiny);
	}

	while(s.size()) s.pop();
	for(int i=0; i<n; ++i){
		if(ans[i]==')'){
			if(s.size()==0u || s.top()!=Data[i]){
				puts("-1");
				return 0;
			} else s.pop();
		} else s.push(Data[i]);
	}
	if(s.size()){
		puts("-1");
		return 0;
	}

	puts(ans);

	return 0;
}

Compilation message

match.cpp: In function 'void read(int&)':
match.cpp:10: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:11: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:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("match.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
match.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", Data);
  ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2139 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2139 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2139 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -