제출 #231422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231422		nicolaalexandra	괄호 문자열 (CEOI16_match)	C++14	100 / 100	1407 ms	2048 KiB

match

#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
char v[DIM],sol[DIM],s[DIM];
int n,i;

void solve (int st, int dr){
    /// in st pun ( si trb sa gasesc )
    if (st >= dr)
        return;
    if (st == dr-1){
        sol[st] = '(';
        sol[dr] = ')';
        return;
    }

    sol[st] = '(';
    int val = v[st] - 'a';
    int i, k = 0;

    for (i=dr;i>st;i--){
        if (!k && v[i] == v[st])
            break;
        if (k && s[k] == v[i])
            k--;
        else s[++k] = v[i];
    }

    sol[i] = ')';
    solve (st+1,i-1);
    solve (i+1,dr);
}

int main (){

    //ifstream cin ("match.in");
    //ofstream cout ("match.out");

    cin>>v+1;
    n = strlen (v+1);

    /// verific daca am solutie
    int k = 0;
    s[++k] = v[1];
    for (i=2;i<=n;i++){
        if (k && s[k] == v[i])
            k--;
        else s[++k] = v[i];
    }

    if (k){
        cout<<-1;
        return 0;
    }

    /*for (i=1;i<=n;i++)
        poz[v[i]-'a'].push_back(i);

    for (i=0;i<26;i++)
        reverse (poz[i].begin(),poz[i].end());*/

    solve (1,n);

    for (i=1;i<=n;i++)
        cout<<sol[i];

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

match.cpp: In function 'void solve(int, int)':
match.cpp:18:9: warning: unused variable 'val' [-Wunused-variable]
     int val = v[st] - 'a';
         ^~~
match.cpp: In function 'int main()':
match.cpp:39:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>v+1;
          ~^~

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