oj.uz

Submission #75172

# Submission time Handle Problem Language Result Execution time Memory
75172 2018-09-08T14:52:24 Z born2rule Match (CEOI16_match) C++14
100 / 100
 384 ms 17072 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=100005,L=26;
int pre[L][N];
string s;
string solve(int l,int r)
{
  assert(((r-l)&1)==1);
  if(s[l]==s[r])
    {
      string ans="(";
      if(r-1>l+1) ans+=solve(l+1,r-1);
      ans+=")";
      return ans;
    }
  int ind=pre[s[l]-'a'][r];
  assert(ind>l);
  string ans="(";
  if(ind-1>l+1) ans+=solve(l+1,ind-1);
  ans+=")";
  if(r>ind+1) ans+=solve(ind+1,r);
  return ans;
}
bool check(string s,int n)
{
  stack<int> st;
  rep(i,1,n+1)
    {
      if(st.empty() || s[st.top()]!=s[i]) st.push(i);
      else st.pop();
    }
  if(!st.empty())
    {
      cout<<-1<<endl;
      exit(0);
    }
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  cin>>s;
  int n=sz(s);
  s="#"+s;
  check(s,n);
  rep(i,3,n+1)
    {
      rep(j,0,26)
	{
	  if(s[i]==s[i-1])
	    {
	      if(((int)(s[i-2]-'a'))==j)
		pre[j][i]=i-2;
	      else
		pre[j][i]=pre[j][i-2];
	    }
	  else
	    {
	      int tmp=pre[(int)(s[i]-'a')][i-1];
	      if(!tmp) continue;
	      tmp--;
	      if(!tmp) continue;
	      if(((int)(s[tmp]-'a'))==j)
		{
		  pre[j][i]=tmp;
		  continue;
		}
	      pre[j][i]=pre[j][tmp];
	    }
	}
    }
  cout<<solve(1,n)<<endl;
  return 0 ;
}

Compilation message

match.cpp: In function 'bool check(std::__cxx11::string, int)':
match.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 932 KB Output is correct
7 Correct 3 ms 952 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 932 KB Output is correct
7 Correct 3 ms 952 KB Output is correct
8 Correct 4 ms 1340 KB Output is correct
9 Correct 5 ms 1728 KB Output is correct
10 Correct 5 ms 1728 KB Output is correct
11 Correct 6 ms 1964 KB Output is correct
12 Correct 74 ms 9540 KB Output is correct
13 Correct 88 ms 10440 KB Output is correct
14 Correct 162 ms 12140 KB Output is correct
15 Correct 350 ms 14360 KB Output is correct
16 Correct 384 ms 14360 KB Output is correct
17 Correct 231 ms 14924 KB Output is correct
18 Correct 260 ms 14924 KB Output is correct
19 Correct 172 ms 14924 KB Output is correct
20 Correct 98 ms 14924 KB Output is correct
21 Correct 298 ms 17072 KB Output is correct