Submission #874904

#	Time	Username	Problem	Language	Result	Execution time	Memory
874904		Sir_Ahmed_Imran	Match (CEOI16_match)	C++17	37 / 100	2096 ms	509264 KiB

match

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define li long int
#define ld long double
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define pic pair<int,char>
#define all(x) (x).begin(),(x).end()
#define sum(a) accumulate(all(a),0)
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define terminator main
#define N 20001
int dp[N][N];
void solve(){
    string a;
    int n,m,o,p,q,r;
    cin>>a;
    n=a.size();
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            dp[i][j]=0;
    for(int j=1;j<n;j++){
        for(int i=0;i<n-j;i++){
            dp[i][i+j]=(a[i]==a[i+j] && 
            (dp[i+1][i+j-1] || j==1));
            for(int k=i+2;k<i+j;k++)
                dp[i][i+j]|=(dp[i][k-1] && dp[k][i+j]);
        }
    }
    if(!dp[0][n-1]){
        cout<<-1;
        return;
    }
    set<int> s{n};
    for(int i=0;i<n;i++){
        o=0;
        for(int j=i+1;j<*s.lower_bound(i);j++){
            if((dp[i+1][j-1] || j-i==1) 
            && a[i]==a[j] && a[i]!=')') o=j;
        }
        if(o){
            s.add(o);
            a[i]='(';
            a[o]=')';
        }
        else a[i]=')';
        cout<<a[i];
    }
}
int terminator(){
    L0TA;
    solve();
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'void solve()':
match.cpp:22:11: warning: unused variable 'm' [-Wunused-variable]
   22 |     int n,m,o,p,q,r;
      |           ^
match.cpp:22:15: warning: unused variable 'p' [-Wunused-variable]
   22 |     int n,m,o,p,q,r;
      |               ^
match.cpp:22:17: warning: unused variable 'q' [-Wunused-variable]
   22 |     int n,m,o,p,q,r;
      |                 ^
match.cpp:22:19: warning: unused variable 'r' [-Wunused-variable]
   22 |     int n,m,o,p,q,r;
      |                   ^

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