oj.uz

답안 #25520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25520 2017-06-22T18:00:02 Z chpipis 괄호 문자열 (CEOI16_match) C++11
37 / 100
 2000 ms 2316 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 1e5 + 5;

char str[MAXN], ans[MAXN];
char temp[MAXN];
int n;

void check(int pos) {
    if (ans[pos] == '(') return;
    stack<char> stk;
    stk.push(str[0]);
    temp[0] = ans[0];
    int i = 1;
    for (; i < pos; i++) {
        if (ans[i] == ')') {
            stk.pop();
        } else {
            stk.push(str[i]);
        }
        temp[i] = ans[i];
    }
    stk.push(str[i]);
    temp[i] = '(';
    for (i++; i < n; i++) {
        if (!stk.empty() && stk.top() == str[i]) {
            stk.pop();
            temp[i] = ')';
        } else {
            stk.push(str[i]);
            temp[i] = '(';
        }
    }
    if (!stk.empty()) return;
    //printf("stack is empty so i copy %s\n", temp);
    strcpy(ans, temp);
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    scanf("%s", str);
    n = strlen(str);
    if (n & 1)
        puts("-1");
    else {
        stack<char> stk;
        stk.push(str[0]);
        ans[0] = '(';
        for (int i = 1; i < n; i++) {
            if (!stk.empty() && stk.top() == str[i]) {
                stk.pop();
                ans[i] = ')';
            } else {
                stk.push(str[i]);
                ans[i] = '(';
            }
        }
        if (!stk.empty())
            puts("-1");
        else {
            for (int i = 0; i < n; i++)
                check(i);
            puts(ans);
        }
    }
    return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:91:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str);
                     ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2316 KB Output is correct
2 Correct 0 ms 2316 KB Output is correct
3 Correct 0 ms 2316 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2316 KB Output is correct
2 Correct 0 ms 2316 KB Output is correct
3 Correct 0 ms 2316 KB Output is correct
4 Correct 0 ms 2316 KB Output is correct
5 Correct 0 ms 2316 KB Output is correct
6 Correct 3 ms 2316 KB Output is correct
7 Correct 9 ms 2316 KB Output is correct

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2316 KB Output is correct
2 Correct 0 ms 2316 KB Output is correct
3 Correct 0 ms 2316 KB Output is correct
4 Correct 0 ms 2316 KB Output is correct
5 Correct 0 ms 2316 KB Output is correct
6 Correct 3 ms 2316 KB Output is correct
7 Correct 9 ms 2316 KB Output is correct
8 Correct 156 ms 2316 KB Output is correct
9 Correct 139 ms 2316 KB Output is correct
10 Correct 86 ms 2316 KB Output is correct
11 Correct 76 ms 2316 KB Output is correct
12 Execution timed out 2000 ms 2316 KB Execution timed out
13 Halted 0 ms 0 KB -