oj.uz

Submission #874904

# Submission time Handle Problem Language Result Execution time Memory
874904 2023-11-18T05:07:13 Z Sir_Ahmed_Imran Match (CEOI16_match) C++17
37 / 100
 2000 ms 509264 KB 
                              ///~~~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

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.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 118 ms 76396 KB Output is correct
5 Correct 137 ms 80508 KB Output is correct
6 Correct 553 ms 119484 KB Output is correct
7 Correct 976 ms 158480 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 118 ms 76396 KB Output is correct
5 Correct 137 ms 80508 KB Output is correct
6 Correct 553 ms 119484 KB Output is correct
7 Correct 976 ms 158480 KB Output is correct
8 Execution timed out 2096 ms 509264 KB Time limit exceeded
9 Halted 0 ms 0 KB -