Submission #1168967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168967		mmmmge1234	Match (CEOI16_match)	C++20	100 / 100	39 ms	28228 KiB

match

#include <bits/stdc++.h>
using namespace std;

#define st first
#define nd second

string s;
long long dp[100005][26];

string solve(long long l, long long r){
        if(l > r) return "";
        return "(" + solve(l + 1, dp[r][s[l] - 'a'] - 1) + ")" + solve(dp[r][s[l] - 'a'] + 1, r);
}

int main(){
        if(fopen("stop.inp" , "r")){
                freopen("stop.inp", "r", stdin);
                freopen("stop.out", "w", stdout);
        }
        cin.tie(0)->sync_with_stdio(0);
        cout.tie(0)->sync_with_stdio(0);
        cin >> s;
        long long n = (long long)s.size();
        s = '0' + s;
        stack<long long> st;
        for(long long i = 1; i <= n; i++){
                if(!st.empty() && st.top() == s[i]) st.pop();
                else st.push(s[i]);
        }
        if(!st.empty()){
                cout << -1 << '\n';
                return 0;
        }
        for(long long i = 2; i <= n; i++){
                for(long long j = 0; j < 26; j++){
                        if(j + 'a' == s[i]) dp[i][j] = i;
                        else dp[i][j] = (dp[i - 1][s[i] - 'a'] - 1 < 0) ? 0 : dp[dp[i - 1][s[i] - 'a'] - 1][j];
                }
        }
        cout << solve(1, n) << '\n';
        return 0;
}

//I hate every single person in and not in this room, farewell.

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen("stop.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
match.cpp:18:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 freopen("stop.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63