Submission #580169

#	Time	Username	Problem	Language	Result	Execution time	Memory
580169		guka415	Match (CEOI16_match)	C++14	0 / 100	1 ms	212 KiB

match

#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 (stderr)

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
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63