Submission #798113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
798113	2023-07-30T11:24:00 Z	RecursiveCo	Match (CEOI16_match)	C++14	0 / 100	1 ms	212 KB

match

// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long int

signed main() {
    improvePerformance;
    string s;
    cin >> s;
    int n = s.size();
    vector<char> res(n);
    map<char, vector<int>> chars;
    forto(n, i) chars[s[i]].push_back(i);
    bool can = true;
    for (auto it = chars.begin(); it != chars.end(); it++) {
        vector<int> ind = it->second;
        if (ind.size() % 2) {
            can = false;
            break;
        }
        forto(ind.size(), i) {
            if (i < ind.size() / 2) res[ind[i]] = '(';
            else res[ind[i]] = ')';
        }
    }
    if (can) {
        int balance = 0;
        forto(n, i) {
            if (res[i] == '(') balance++;
            else balance--;
            if (balance < 0) can = false;
        }
        if (balance != 0) can = false;
    }
    vector<int> matches(n, -1);
    stack<int> st;
    if (can) {
        forto(n, i) {
            if (res[i] == '(') st.push(i);
            else {
                int top = st.top();
                matches[top] = i;
                matches[i] = top;
                st.pop();
            }
        }
        forto(n, i) {
            char first = s[i];
            char second = s[matches[i]];
            if (first != second) {
                can = false;
                break;
            }
        }
    }
    if (!can) out(-1);
    else {
        forto(n, i) {
            out(res[i]);
        }
    }
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
match.cpp:27:5: note: in expansion of macro 'forto'
   27 |     forto(n, i) chars[s[i]].push_back(i);
      |     ^~~~~
match.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
match.cpp:35:9: note: in expansion of macro 'forto'
   35 |         forto(ind.size(), i) {
      |         ^~~~~
match.cpp:15:52: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                              ~~~~~~^~~~~~~~
match.cpp:35:9: note: in expansion of macro 'forto'
   35 |         forto(ind.size(), i) {
      |         ^~~~~
match.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             if (i < ind.size() / 2) res[ind[i]] = '(';
      |                 ~~^~~~~~~~~~~~~~~~
match.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
match.cpp:42:9: note: in expansion of macro 'forto'
   42 |         forto(n, i) {
      |         ^~~~~
match.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
match.cpp:52:9: note: in expansion of macro 'forto'
   52 |         forto(n, i) {
      |         ^~~~~
match.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
match.cpp:61:9: note: in expansion of macro 'forto'
   61 |         forto(n, i) {
      |         ^~~~~
match.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
match.cpp:72:9: note: in expansion of macro 'forto'
   72 |         forto(n, i) {
      |         ^~~~~

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-