oj.uz

Submission #580169

# Submission time Handle Problem Language Result Execution time Memory
580169 2022-06-20T16:35:04 Z guka415 Match (CEOI16_match) C++14
0 / 100
 1 ms 212 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define _CRT_SECURE_NO_WARNINGS
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define ff first
#define ss second

#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <numeric>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef vector<int> vi;
typedef pair<ld, ld> pld;

bool valid(string t, string s) {
    stack<int> stk;
    int n = t.length();
    foru(i, 0, n) {
        if (t[i] == '(') {
            stk.push(i);
        }
        else {
            if (stk.empty())return 0;
            else if (s[stk.top()] != s[i])return 0;
            stk.pop();
        }
    }
    return stk.empty();
}

int main() {
    fast;
    //freopen("match.in", "r", stdin);
    //freopen("match.out", "w", stdout);
    int n;
    string s;
    cin >> s; n = s.length();
    vector<int> cnts(26, 0), seen = cnts;
    bool bad = 0;
    for (char c : s)cnts[c - 'a']++;
    for (int x : cnts) {
        if (x & 1)bad = 1;
    }
    if (bad) {
        cout << -1 << '\n';
        return 0;
    }
    string t = "";
    for (char c : s) {
        if (seen[c - 'a'] * 2 < cnts[c - 'a']) {
            seen[c - 'a']++;
            t += '(';
        }
        else t += ')';
    }
    if (valid(t, s))cout << t;
    else cout << -1 << '\n';
    return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:54:9: warning: variable 'n' set but not used [-Wunused-but-set-variable]
   54 |     int n;
      |         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -