oj.uz

답안 #1117819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117819 2024-11-24T08:40:15 Z vjudge1 괄호 문자열 (CEOI16_match) C++17
0 / 100
 1 ms 336 KB 
#include "bits/stdc++.h"

using namespace std;

const int mxN = 100005;
const int mxAl = 26;

set<int> pos[mxAl];
char ans[mxN];

int main() {
    string S;
    cin >> S;

    int N = S.size();
    for (int i = 0; i < N; i ++) {
        int c = S[i] - 'a';
        if (!pos[c].empty()) {
            int last = *pos[c].rbegin();
            if (~(i - last) & 1) {
                cout << -1 << endl;
                return 0;
            }
        }
        pos[c].insert(i);
    }

    for (int i = 0; i < mxAl; i ++) {
        if ((int)pos[i].size() & 1) {
            cout << -1 << endl;
            return 0;
        }
    }

    int sz = N;
    while (sz) {
        for (int i = 0; i < mxAl; i ++) {
            if (!pos[i].empty()) {
                ans[*pos[i].begin()] = '(';
                ans[*pos[i].rbegin()] = ')';
                pos[i].erase(pos[i].begin());
                pos[i].erase(--pos[i].end());
                sz -= 2;
            }
        }
    }

    int balance = 0;
    for (int i = 0; i < N; i ++) {
        if ('(' == ans[i]) {
            balance ++;
        } else {
            balance --;
        }
        if (0 > balance) {
            cout << -1 << endl;
            return 0;
        }
    }
    if (balance) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 0; i < N; i ++) {
        cout << ans[i];
    }
    cout << endl;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -