oj.uz

답안 #589208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589208 2022-07-04T10:34:05 Z andrei_boaca 괄호 문자열 (CEOI16_match) C++14
100 / 100
 112 ms 69068 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int baza=29,invbaza=758620695;
const int mod=1e9+7;
int n;
string s,sol;
vector<char> st;
vector<int> mypoz[27][2][50005];
map<int,int> nrm;
int nxt[100005];
int sum[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    n=s.size();
    s=" "+s;
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    int nr=1;
    ll h=0;
    nrm[h]=1;
    sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.back()==s[i])
            st.pop_back();
        else
            st.push_back(s[i]);
    }
    if(!st.empty())
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.back()==s[i])
        {
            st.pop_back();
            h-=(s[i]-'a'+1);
            h=(1LL*h*invbaza)%mod;
        }
        else
        {
            h=((1LL*h*baza)+s[i]-'a'+1)%mod;
            st.push_back(s[i]);
        }
        if(nrm[h]==0)
        {
            nr++;
            nrm[h]=nr;
        }
        sum[i]=nrm[h];
        mypoz[s[i]-'a'+1][i%2][sum[i]].push_back(i);
    }
    vector<int> last;
    sol.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        if(sol[i]!=')')
        {
            sol[i]='(';
            int maxpoz=n+1;
            if(!last.empty())
                maxpoz=last.back();
            int par=1-i%2;
            int lit=s[i]-'a'+1;
            int lft=0;
            int rgt=mypoz[lit][par][sum[i-1]].size();
            rgt--;
            int poz=0;
            while(lft<=rgt)
            {
                int mij=(lft+rgt)/2;
                if(mypoz[lit][par][sum[i-1]][mij]<maxpoz)
                {
                    poz=mypoz[lit][par][sum[i-1]][mij];
                    lft=mij+1;
                }
                else
                    rgt=mij-1;
            }
            sol[poz]=')';
            last.push_back(poz);
        }
        else
            last.pop_back();
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 63692 KB Output is correct
2 Correct 44 ms 63624 KB Output is correct
3 Correct 41 ms 63680 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 63692 KB Output is correct
2 Correct 44 ms 63624 KB Output is correct
3 Correct 41 ms 63680 KB Output is correct
4 Correct 35 ms 63736 KB Output is correct
5 Correct 32 ms 63768 KB Output is correct
6 Correct 38 ms 63724 KB Output is correct
7 Correct 39 ms 63776 KB Output is correct

Subtask #3
63.0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 63692 KB Output is correct
2 Correct 44 ms 63624 KB Output is correct
3 Correct 41 ms 63680 KB Output is correct
4 Correct 35 ms 63736 KB Output is correct
5 Correct 32 ms 63768 KB Output is correct
6 Correct 38 ms 63724 KB Output is correct
7 Correct 39 ms 63776 KB Output is correct
8 Correct 42 ms 64000 KB Output is correct
9 Correct 45 ms 64028 KB Output is correct
10 Correct 35 ms 64144 KB Output is correct
11 Correct 35 ms 64076 KB Output is correct
12 Correct 72 ms 67324 KB Output is correct
13 Correct 95 ms 67720 KB Output is correct
14 Correct 112 ms 68000 KB Output is correct
15 Correct 43 ms 64944 KB Output is correct
16 Correct 49 ms 64992 KB Output is correct
17 Correct 63 ms 66968 KB Output is correct
18 Correct 41 ms 64940 KB Output is correct
19 Correct 105 ms 69068 KB Output is correct
20 Correct 75 ms 67472 KB Output is correct
21 Correct 100 ms 68964 KB Output is correct