oj.uz

Submission #1032721

# Submission time Handle Problem Language Result Execution time Memory
1032721 2024-07-24T06:53:47 Z 김은성(#10965) Match (CEOI16_match) C++17
100 / 100
 1235 ms 920 KB 
#include <bits/stdc++.h>
using namespace std;
char s[100009], t[100009];
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();
}
int inverse(int init, int idx, vector<char> vec){
    int i, j = 0;
    vector<char> st;
    for(i=init; i>=idx; i--){
        if(j < vec.size() && st.empty() && 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 i;
    }
    return -1;
}
int main(){
    int i;
    scanf(" %s", s);
    n = strlen(s);
    vector<char> st;
    if(!possible(0, st)){
        printf("-1\n");
        return 0;
    }
    vector<int> inv;
    inv.push_back(n);
    for(i=0; i<n; i++){
        st.push_back(s[i]);
        t[i] = '(';
        int temp = inverse(inv.back()-1, i, {st.back()});
       //printf("temp=%d\n", temp);
        if(temp==-1){
            t[i] = ')';
            st.pop_back();
            st.pop_back();
            inv.pop_back();
        }
        else{
            inv.push_back(temp);
        }
    }
    printf("%s\n", t);
    return 0;
}

Compilation message

match.cpp: In function 'int inverse(int, int, std::vector<char>)':
match.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(j < vec.size() && st.empty() && vec[j] == s[i])
      |            ~~^~~~~~~~~~~~
match.cpp:27:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if(j==vec.size())
      |            ~^~~~~~~~~~~~
match.cpp: In function 'int main()':
match.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 356 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 356 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Correct 51 ms 604 KB Output is correct
13 Correct 28 ms 840 KB Output is correct
14 Correct 365 ms 856 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 864 KB Output is correct
17 Correct 43 ms 920 KB Output is correct
18 Correct 7 ms 860 KB Output is correct
19 Correct 568 ms 916 KB Output is correct
20 Correct 233 ms 804 KB Output is correct
21 Correct 1235 ms 856 KB Output is correct