oj.uz

Submission #1032713

# Submission time Handle Problem Language Result Execution time Memory
1032713 2024-07-24T06:43:00 Z 김은성(#10965) Match (CEOI16_match) C++17
10 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
char s[100009], t[100009];
int cnt[128], cur[128];
int n;
bool possible(int idx, vector<char> st){
    int i;
    for(i=idx; i<n; i++){
        if(!st.empty() && st.back() == s[i])
            st.pop_back();
        else
            st.push_back(s[i]);
    }
    return st.empty();
}
bool inverse(int idx, vector<char> vec){
    int i, j = 0;
    vector<char> st;
    for(i=n-1; i>=idx; i--){
        if(j < vec.size() && vec[j] == s[i])
            j++;
        else{
            if(!st.empty() && st.back() == s[i])
                st.pop_back();
            else
                st.push_back(s[i]);
        }
        if(j==vec.size())
            return 1;
    }
    return 0;
}
int main(){
    int i;
    scanf(" %s", s);
    n = strlen(s);
    for(i=0; i<n; i++)
        cnt[s[i]]++;
    vector<char> st;
    if(!possible(0, st)){
        printf("-1\n");
        return 0;
    }
    for(i=0; i<n; i++){
        st.push_back(s[i]);
        t[i] = '(';
        if(st.size()>1 && st[st.size()-2] == s[i]){
            if(cur[s[i]] >= cnt[s[i]]/2 || !inverse(i+1, st)){
                t[i] = ')';
                cur[s[i]] -= 2;
                st.pop_back();
                st.pop_back();
            }
        }
        cur[s[i]]++;
    }
    printf("%s\n", t);
    return 0;
}

Compilation message

match.cpp: In function 'bool inverse(int, std::vector<char>)':
match.cpp:20:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if(j < vec.size() && vec[j] == s[i])
      |            ~~^~~~~~~~~~~~
match.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if(j==vec.size())
      |            ~^~~~~~~~~~~~
match.cpp: In function 'int main()':
match.cpp:38:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |         cnt[s[i]]++;
      |             ~~~^
match.cpp:48:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |             if(cur[s[i]] >= cnt[s[i]]/2 || !inverse(i+1, st)){
      |                    ~~~^
match.cpp:48:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |             if(cur[s[i]] >= cnt[s[i]]/2 || !inverse(i+1, st)){
      |                                 ~~~^
match.cpp:50:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |                 cur[s[i]] -= 2;
      |                     ~~~^
match.cpp:55:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |         cur[s[i]]++;
      |             ~~~^
match.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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