oj.uz

Submission #260531

# Submission time Handle Problem Language Result Execution time Memory
260531 2020-08-10T13:23:34 Z kimbj0709 Match (CEOI16_match) C++14
10 / 100
 1 ms 1280 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
int lastpos[maxn][26];
string input;
vector<int> out(maxn,0);
void recursive(int l,int r){
  if(l>=r){
    return;
  }
  if(input.at(l)==input.at(r)){
    out[r] = 1;
    recursive(l+1,r-1);
    return;
  }
  int pos = lastpos[r][input.at(l)-'a'];
  out[pos] = 1;
  recursive(l+1,pos-1);
  recursive(pos+1,r);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  cin >> input;
  stack<int> stack1;
  stack1.push(0);
  for(int i=1;i<input.length();i++){
    if(stack1.size()!=0&&input.at(stack1.top())==input.at(i)){
      stack1.pop();
    }
    else{
      stack1.push(i);
    }
  }
  if(stack1.size()!=0){
    cout << -1;
    return 0;
  }
  for(int i=0;i<26;i++){
    int last = -1;
    for(int j=0;j<input.length();j++){
      if(input.at(j)==('a'+i)){
        last = j;
      }
      lastpos[j][i] = last; 
    }
  }
  recursive(0,input.length()-1);
  for(int i=0;i<input.length();i++){
    if(out[i]==1){
      cout << ')';
    }
    else{
      cout << '(';
    }
  }

}

Compilation message

match.cpp: In function 'int32_t main()':
match.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<input.length();i++){
               ~^~~~~~~~~~~~~~~
match.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<input.length();j++){
                 ~^~~~~~~~~~~~~~~
match.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<input.length();i++){
               ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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