Submission #90487

#	Time	Username	Problem	Language	Result	Execution time	Memory
90487		tincamatei	Match (CEOI16_match)	C++14	0 / 100	2 ms	500 KiB

match

#include <bits/stdc++.h>

using namespace std;

int st[100000], top;
int nextPoz[26][100001];

vector<int> poz[26];

bool solve(int l, int r, string &str, string &par) {
  int nr = 0, cnt = 0, lastPoz = 0;
  bool lastP = false;
  bool rez = true;


  if(l == r + 1)
    return true;
  if(r == str.size())
    return false;

  for(int i = l; i <= r; i = nextPoz[str[i] - 'a'][i]) {
    ++nr;
    if(nextPoz[str[i] - 'a'][i] <= r)
      rez &= solve(i + 1, nextPoz[str[i] - 'a'][i] - 1, str, par);
    if(i == r)
      lastP = true;
    lastPoz = i;
  }

  if(!lastP)
    rez &= solve(lastPoz + 1, r, str, par);

  if(nr % 2 == 1)
    return false;
  for(int i = l; i <= r; i = nextPoz[str[i] - 'a'][i])
    if(cnt++ < nr / 2)
      par[i] = '(';
    else
      par[i] = ')';
  return true & rez;
}

int main() {
  string str, par;

  cin >> str;

  for(int i = 0; i < str.size(); ++i)
    poz[str[i] - 'a'].push_back(i);

  par.resize(str.size());

  for(int j = 0; j < 26; ++j) {
    int lastP = str.size();
    for(int i = str.size() - 1; i >= 0; --i) {
      nextPoz[j][i] = lastP;
      if(str[i] == j + 'a')
        lastP = i;
    }
  }

  if(solve(0, str.size() - 1, str, par))
    cout << par;
  else
    cout << -1;
  return 0;
}

Compilation message (stderr)

match.cpp: In function 'bool solve(int, int, std::__cxx11::string&, std::__cxx11::string&)':
match.cpp:18:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r == str.size())
      ~~^~~~~~~~~~~~~
match.cpp: In function 'int main()':
match.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < str.size(); ++i)
                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63