oj.uz

답안 #589199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589199 2022-07-04T10:27:35 Z andrei_boaca 괄호 문자열 (CEOI16_match) C++14
100 / 100
 218 ms 263144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const ll baza=29,invbaza=758620695;
const ll mod=1e9+7;
int n;
string s,sol;
vector<char> st;
set<int> mypoz[27][2][100005];
map<ll,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=(h*invbaza)%mod;
        }
        else
        {
            h=((h*baza)%mod+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]].insert(i);
    }
    set<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.begin();
            int par=1-i%2;
            int lit=s[i]-'a'+1;
            auto it=prev(mypoz[lit][par][sum[i-1]].lower_bound(maxpoz));
            int poz=(*it);
            sol[poz]=')';
            last.insert(poz);
            //mypoz[lit][par][sum[i-1]].erase(it);
        }
        else
            last.erase(i);
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 253940 KB Output is correct
2 Correct 123 ms 253916 KB Output is correct
3 Correct 142 ms 253848 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 253940 KB Output is correct
2 Correct 123 ms 253916 KB Output is correct
3 Correct 142 ms 253848 KB Output is correct
4 Correct 146 ms 254012 KB Output is correct
5 Correct 125 ms 254024 KB Output is correct
6 Correct 123 ms 253984 KB Output is correct
7 Correct 167 ms 254004 KB Output is correct

Subtask #3
63.0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 253940 KB Output is correct
2 Correct 123 ms 253916 KB Output is correct
3 Correct 142 ms 253848 KB Output is correct
4 Correct 146 ms 254012 KB Output is correct
5 Correct 125 ms 254024 KB Output is correct
6 Correct 123 ms 253984 KB Output is correct
7 Correct 167 ms 254004 KB Output is correct
8 Correct 137 ms 254508 KB Output is correct
9 Correct 119 ms 254504 KB Output is correct
10 Correct 119 ms 254472 KB Output is correct
11 Correct 126 ms 254628 KB Output is correct
12 Correct 177 ms 259656 KB Output is correct
13 Correct 186 ms 260268 KB Output is correct
14 Correct 218 ms 260828 KB Output is correct
15 Correct 152 ms 259828 KB Output is correct
16 Correct 153 ms 259776 KB Output is correct
17 Correct 196 ms 261408 KB Output is correct
18 Correct 170 ms 259400 KB Output is correct
19 Correct 190 ms 262572 KB Output is correct
20 Correct 162 ms 259856 KB Output is correct
21 Correct 190 ms 263144 KB Output is correct