Submission #244682

#	Time	Username	Problem	Language	Result	Execution time	Memory
244682		evpipis	Match (CEOI16_match)	C++11	0 / 100	5 ms	384 KiB

match

#include <bits/stdc++.h>
using namespace std;

const int len = 1e5+5;
char str[len], out[len];
int pref[len];

int solve(int l, int r, int bit){
    if (l > r) return 1;

    int k = 0;
    for (int i = l+1; i <= r; i++)
        if (str[i] == str[l] && pref[i] == bit) k = i;

    if (!k) return 0;

    out[l] = '(';
    out[k] = ')';

    return solve(l+1, k-1, bit^(1<<(str[l]-'a')))|solve(k+1, r, bit);
}

int main(){
    scanf("%s", str);
    int n = strlen(str);

    for (int i = 0, bit = 0; i < n; i++){
        bit ^= (1<<(str[i]-'a'));
        pref[i] = bit;
    }

    int ans = solve(0, n-1, 0);
    if (!ans){
        printf("-1\n");
        return 0;
    }

    for (int i = 0; i < n; i++)
        printf("%c", out[i]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:24:10: 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