Submission #25522

#	Time	Username	Problem	Language	Result	Execution time	Memory
25522		chpipis	Match (CEOI16_match)	C++11	0 / 100	0 ms	3880 KiB

match

#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;
const int INF = 1e9;

char str[MAXN], ans[MAXN];
char temp[MAXN];
int n;
vi where[30];

int st[MAXN << 2];

void printall() {
#ifdef LOCAL_MACHINE
    printf("current prefixes: ");
    for (int i = 0; i < n; i++)
        printf("%d ", st[i]);
    puts("");
#endif
}

#define params int p, int L, int R

void add(params, int i, int j, int val) {
    for (int k = i; k <= j; k++)
        st[k] += val;
}

int query(params, int i, int j) {
    int res = INF;
    for (int k = i; k <= j; k++)
        res = min(res, st[k]);
    return res;
}

void check(int pos) {
    if (ans[pos] == '(') return;
    int lo = lower_bound(all(where[str[pos] - 'a']), pos) - where[str[pos] - 'a'].begin() + 1,
        hi = (int)where[str[pos] - 'a'].size() - 1, res = -1;
    int pref = query(1, 0, n - 1, pos, pos);
    //fprintf(stderr, "for pos = %d, pref = %d\n", pos, pref);
    printall();
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        int cur = where[str[pos] - 'a'][mid];
        int sum = query(1, 0, n - 1, cur - 1, cur - 1) - pref;
        int mn = query(1, 0, n - 1, pos + 1, cur - 1) - pref;
        if (ans[cur] == '(' && sum == 0 && mn >= 0) {
            lo = mid + 1;
            res = cur;
        } else {
            hi = mid - 1;
        }
    }
    if (res == -1) return;
    add(1, 0, n - 1, pos, res - 1, 2);
    ans[pos] = '(';
    ans[res] = ')';
#if 0
    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);
#endif
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    scanf("%s", str);
    n = strlen(str);
    if (n & 1)
        puts("-1");
    else {
        for (int i = 0; i < n; i++) {
            where[str[i] - 'a'].pb(i);
        }
        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 {
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += (ans[i] == '(' ? 1 : -1);
                add(1, 0, n - 1, i, i, sum);
            }
            printall();
            for (int i = 0; i < n; i++)
                check(i);
            puts(ans);
        }
    }
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63