oj.uz

답안 #745454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745454 2023-05-20T07:16:45 Z Tenis0206 괄호 문자열 (CEOI16_match) C++11
37 / 100
 2000 ms 26416 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;

int n;
int v[nmax + 5];

bool ok;

char rez[nmax + 5];

int fr[nmax + 5];

void solve(int st, int dr)
{
    if(st > dr)
    {
        return;
    }
    int poz = 0;
    int nrimp = 0;
    stack<int> s;
    for(int i=st; i<=dr; i++)
    {
        ++fr[v[i]];
        if(s.empty() || v[s.top()] != v[i])
        {
            s.push(i);
        }
        else
        {
            s.pop();
        }
        if(i!=st && v[i]==v[st] && s.empty())
        {
            poz = i;
        }
    }
    for(int i=st; i<=dr; i++)
    {
        fr[v[i]] = 0;
    }
    if(!poz)
    {
        ok = false;
        return;
    }
    rez[st] = '(';
    rez[poz] = ')';
    solve(st+1,poz-1);
    solve(poz+1,dr);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
#endif // home
    string s;
    cin>>s;
    n = s.size();
    for(int i=1; i<=n; i++)
    {
        v[i] = s[i - 1];
        ++fr[v[i]];
    }
    ok = true;
    for(int i=1; i<=n; i++)
    {
        if(fr[v[i]] % 2 == 1)
        {
            ok = false;
        }
        fr[v[i]] = 0;
    }
    if(!ok)
    {
        cout<<-1<<'\n';
        return 0;
    }
    solve(1,n);
    if(!ok)
    {
        cout<<-1<<'\n';
        return 0;
    }
    for(int i=1; i<=n; i++)
    {
        cout<<rez[i];
    }
    cout<<'\n';
    return 0;
}

Compilation message

match.cpp: In function 'void solve(int, int)':
match.cpp:23:9: warning: unused variable 'nrimp' [-Wunused-variable]
   23 |     int nrimp = 0;
      |         ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Correct 74 ms 1896 KB Output is correct
10 Correct 44 ms 1504 KB Output is correct
11 Correct 74 ms 2892 KB Output is correct
12 Execution timed out 2090 ms 26416 KB Time limit exceeded
13 Halted 0 ms 0 KB -