oj.uz

Submission #52954

# Submission time Handle Problem Language Result Execution time Memory
52954 2018-06-27T08:48:26 Z 강태규(#1381) Match (CEOI16_match) C++11
100 / 100
 19 ms 11368 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
char str[100001];
char st[100000];
char ans[100001];
int pr[100001][26];

void solve(int s, int e) {
    if (s > e) return;
    if (str[s] == str[e]) {
        ans[s] = '(';
        ans[e] = ')';
        solve(s + 1, e - 1);
    }
    else {
        int m = e - pr[e][str[s]];
        solve(s, m);
        solve(m + 1, e);
    }
}

int main() {
    scanf("%s", str);
    int tp = 0;
    for (int i = 0; str[i]; n = ++i) {
        str[i] -= 'a';
        if (tp && st[tp - 1] == str[i]) --tp;
        else st[tp++] = str[i];
    }
    if (tp) {
        printf("-1\n");
        return 0;
    }
    for (int i = 0; i < 26; ++i) {
        pr[0][i] = 1;
    }
    for (int i = 1; i < n; ++i) {
        if (str[i - 1] == str[i]) pr[i][str[i]] = 1;
        else pr[i][str[i]] = pr[i - 1][str[i]] + 1;
        for (int j = 0; j < 26; ++j) {
            if (str[i] == j) continue;
            if (i <= pr[i][str[i]]) pr[i][j] = i + 1;
            else if (str[i - pr[i][str[i]] - 1] == j)
                pr[i][j] = pr[i][str[i]] + 1;
            else
                pr[i][j] = pr[i - pr[i][str[i]] - 1][j] + pr[i][str[i]] + 1;
        }
    }
    solve(0, n - 1);
    printf(ans);
	return 0;
}

Compilation message

match.cpp: In function 'void solve(int, int)':
match.cpp:35:33: warning: array subscript has type 'char' [-Wchar-subscripts]
         int m = e - pr[e][str[s]];
                                 ^
match.cpp: In function 'int main()':
match.cpp:57:47: warning: array subscript has type 'char' [-Wchar-subscripts]
         if (str[i - 1] == str[i]) pr[i][str[i]] = 1;
                                               ^
match.cpp:58:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         else pr[i][str[i]] = pr[i - 1][str[i]] + 1;
                          ^
match.cpp:58:46: warning: array subscript has type 'char' [-Wchar-subscripts]
         else pr[i][str[i]] = pr[i - 1][str[i]] + 1;
                                              ^
match.cpp:61:34: warning: array subscript has type 'char' [-Wchar-subscripts]
             if (i <= pr[i][str[i]]) pr[i][j] = i + 1;
                                  ^
match.cpp:62:42: warning: array subscript has type 'char' [-Wchar-subscripts]
             else if (str[i - pr[i][str[i]] - 1] == j)
                                          ^
match.cpp:63:40: warning: array subscript has type 'char' [-Wchar-subscripts]
                 pr[i][j] = pr[i][str[i]] + 1;
                                        ^
match.cpp:65:47: warning: array subscript has type 'char' [-Wchar-subscripts]
                 pr[i][j] = pr[i - pr[i][str[i]] - 1][j] + pr[i][str[i]] + 1;
                                               ^
match.cpp:65:71: warning: array subscript has type 'char' [-Wchar-subscripts]
                 pr[i][j] = pr[i - pr[i][str[i]] - 1][j] + pr[i][str[i]] + 1;
                                                                       ^
match.cpp:69:15: warning: format not a string literal and no format arguments [-Wformat-security]
     printf(ans);
               ^
match.cpp:42:10: 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 3 ms 712 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 3 ms 712 KB Output is correct
8 Correct 3 ms 1224 KB Output is correct
9 Correct 3 ms 1356 KB Output is correct
10 Correct 3 ms 1396 KB Output is correct
11 Correct 3 ms 1396 KB Output is correct
12 Correct 12 ms 6976 KB Output is correct
13 Correct 12 ms 7512 KB Output is correct
14 Correct 14 ms 8136 KB Output is correct
15 Correct 15 ms 9064 KB Output is correct
16 Correct 14 ms 9064 KB Output is correct
17 Correct 14 ms 9636 KB Output is correct
18 Correct 17 ms 10088 KB Output is correct
19 Correct 19 ms 10728 KB Output is correct
20 Correct 12 ms 10728 KB Output is correct
21 Correct 19 ms 11368 KB Output is correct