Submission #475650

#	Time	Username	Problem	Language	Result	Execution time	Memory
475650		ZaZo_	Match (CEOI16_match)	C++14	0 / 100	0 ms	204 KiB

match

#include <bits/stdc++.h>
#define HID ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define all(v) v.begin(),v.end()
const int N = 2010 , INF = 1e15;
using namespace std;
string ss , ans;
vector<set<int>>v(27);
vector<int>s;
bool check(int start , int end)
{
  ans[start]='(' , ans[end]=')';
  for(int i = start+1 ; i < end ; i++)
  {
    if(v[s[i]].size()==0) return cout<<"-1",0;
    auto it = v[s[i]].end();
    it--;
    if(*it == i) return true;
    v[s[i]].erase(it);
    check(i , *it);
    i = *it;
  }
  return false;
}
int32_t main() {
  HID
  cin >> ss;
  ans=ss;
  for(int i = 0 ; i < ss.size() ; i++)
  {
    s.push_back(ss[i]-'a');
  }
  for(int i = 0 ; i < s.size() ; i++)
    v[s[i]].insert(i);
  for(int i = 0 ; i < s.size() ; i++)
  {
    if(v[s[i]].size()==0) return cout<<"-1",0;
    auto it = v[s[i]].end();
    it--;
    if(*it == i) return cout<<"-1",0;
    v[s[i]].erase(it);
    bool ok = check(i , *it);
    if(ok)
      return cout<<"-1",0;
    i=*it;
  }
  cout<<ans<<endl;
}

Compilation message (stderr)

match.cpp: In function 'int32_t main()':
match.cpp:29:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i = 0 ; i < ss.size() ; i++)
      |                   ~~^~~~~~~~~~~
match.cpp:33:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int i = 0 ; i < s.size() ; i++)
      |                   ~~^~~~~~~~~~
match.cpp:35:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i = 0 ; i < s.size() ; i++)
      |                   ~~^~~~~~~~~~

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