oj.uz

Submission #236970

# Submission time Handle Problem Language Result Execution time Memory
236970 2020-06-04T06:46:46 Z Sorting Match (CEOI16_match) C++14
37 / 100
 2000 ms 5248 KB 
#include <bits/stdc++.h>

using namespace std;

string s;
int n;

bool check(string &curr, int pos){
    if(curr == "" && pos == n)
        return true;
    if(curr.size() > (n - pos))
        return false;

    if(curr != "" && curr.back() == s[pos]){
        curr.pop_back();
        bool answer = check(curr, pos + 1);
        curr += s[pos];

        return answer;
    }

    curr += s[pos];
    bool answer = check(curr, pos + 1);
    curr.pop_back();

    return answer;
}

void solve(string &answer, int pos){
    if(answer == "" && pos == n)
        return;

    answer += s[pos];
    if(check(answer, pos + 1)){
        solve(answer, pos + 1);
        answer += "(";
        return;
    }
    answer.pop_back();

    if(answer != "" && answer.back() == s[pos]){
        answer.pop_back();
        solve(answer, pos + 1);
        answer += ")";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> s;
    n = s.size();

    string answer = "";
    if(!check(answer, 0)){
        cout << "-1\n";
        return 0;
    }

    solve(answer, 0);

    reverse(answer.begin(), answer.end());
    cout << answer << "\n";
}

Compilation message

match.cpp: In function 'bool check(std::__cxx11::string&, int)':
match.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(curr.size() > (n - pos))
        ~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 18 ms 384 KB Output is correct
5 Correct 21 ms 384 KB Output is correct
6 Correct 30 ms 512 KB Output is correct
7 Correct 62 ms 512 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 18 ms 384 KB Output is correct
5 Correct 21 ms 384 KB Output is correct
6 Correct 30 ms 512 KB Output is correct
7 Correct 62 ms 512 KB Output is correct
8 Correct 688 ms 1024 KB Output is correct
9 Correct 663 ms 1016 KB Output is correct
10 Correct 588 ms 896 KB Output is correct
11 Correct 542 ms 1016 KB Output is correct
12 Execution timed out 2078 ms 5248 KB Time limit exceeded
13 Halted 0 ms 0 KB -