oj.uz

Submission #589196

# Submission time Handle Problem Language Result Execution time Memory
589196 2022-07-04T10:26:11 Z andrei_boaca Match (CEOI16_match) C++14
100 / 100
 182 ms 261964 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

# Verdict Execution time Memory Grader output
1 Correct 130 ms 253940 KB Output is correct
2 Correct 124 ms 253940 KB Output is correct
3 Correct 131 ms 253936 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 253940 KB Output is correct
2 Correct 124 ms 253940 KB Output is correct
3 Correct 131 ms 253936 KB Output is correct
4 Correct 122 ms 253952 KB Output is correct
5 Correct 110 ms 254020 KB Output is correct
6 Correct 109 ms 254004 KB Output is correct
7 Correct 121 ms 254068 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 253940 KB Output is correct
2 Correct 124 ms 253940 KB Output is correct
3 Correct 131 ms 253936 KB Output is correct
4 Correct 122 ms 253952 KB Output is correct
5 Correct 110 ms 254020 KB Output is correct
6 Correct 109 ms 254004 KB Output is correct
7 Correct 121 ms 254068 KB Output is correct
8 Correct 135 ms 254396 KB Output is correct
9 Correct 150 ms 254412 KB Output is correct
10 Correct 127 ms 254476 KB Output is correct
11 Correct 121 ms 254440 KB Output is correct
12 Correct 150 ms 259000 KB Output is correct
13 Correct 154 ms 259432 KB Output is correct
14 Correct 160 ms 259796 KB Output is correct
15 Correct 158 ms 258324 KB Output is correct
16 Correct 156 ms 258348 KB Output is correct
17 Correct 156 ms 259848 KB Output is correct
18 Correct 144 ms 258900 KB Output is correct
19 Correct 176 ms 261696 KB Output is correct
20 Correct 164 ms 258944 KB Output is correct
21 Correct 182 ms 261964 KB Output is correct