Submission #49064

#	Time	Username	Problem	Language	Result	Execution time	Memory
49064		Namnamseo	괄호 문자열 (CEOI16_match)	C++17	0 / 100	2134 ms	524288 KiB

match

#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(){
	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 (stderr)

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: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
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63