oj.uz

Submission #1032657

# Submission time Handle Problem Language Result Execution time Memory
1032657 2024-07-24T05:40:14 Z 정민찬(#10967) Match (CEOI16_match) C++17
10 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

string s;

bool Check(vector<char> st, int idx) {
    for (int i=idx; i<s.size(); i++) {
        if (!st.empty() && st.back() == s[i]) st.pop_back();
        else st.push_back(s[i]);
    }
    return st.empty();
}

int S[100010][26];

int Find(int r, int c) {
    if (S[r][c] == 0) return -1;
    int lo = 0, hi = r;
    while (lo < hi) {
        int mid = lo + hi + 1 >> 1;
        if (S[r][c] - S[mid-1][c]) {
            lo = mid;
        }
        else {
            hi = mid - 1;
        }
    }
    return lo;
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    cin >> s;
    if (!Check({}, 0)) {
        cout << "-1\n";
        return 0;
    }
    int n = s.size();
    for (int i=0; i<n; i++) {
        S[i][s[i]-'a'] ++;
    }
    for (int i=1; i<n; i++) {
        for (int j=0; j<26; j++) {
            S[i][j] += S[i-1][j];
        }
    }
    string ans;
    vector<char> st1;
    vector<int> st2 = {n};
    for (int i=0; i<n; i++) {
        int ret = Find(st2.back()-1, s[i]-'a');
        if (ret == -1 || ret <= i) {
            st2.pop_back();
            ans.push_back(')');
        }
        else {
            ans.push_back('(');
            st2.push_back(ret);
        }
    }
    cout << ans << '\n';
}

Compilation message

match.cpp: In function 'bool Check(std::vector<char>, int)':
match.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=idx; i<s.size(); i++) {
      |                     ~^~~~~~~~~
match.cpp: In function 'int Find(int, int)':
match.cpp:24:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         int mid = lo + hi + 1 >> 1;
      |                   ~~~~~~~~^~~

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 348 KB Output is correct
3 Correct 0 ms 348 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 348 KB Output is correct
3 Correct 0 ms 348 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -