oj.uz

Submission #475650

# Submission time Handle Problem Language Result Execution time Memory
475650 2021-09-23T15:04:21 Z ZaZo_ Match (CEOI16_match) C++14
0 / 100
 0 ms 204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -