oj.uz

Submission #589206

# Submission time Handle Problem Language Result Execution time Memory
589206 2022-07-04T10:33:00 Z andrei_boaca Match (CEOI16_match) C++14
100 / 100
 117 ms 132496 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][100005];
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

# Verdict Execution time Memory Grader output
1 Correct 62 ms 127124 KB Output is correct
2 Correct 62 ms 127076 KB Output is correct
3 Correct 61 ms 127020 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 127124 KB Output is correct
2 Correct 62 ms 127076 KB Output is correct
3 Correct 61 ms 127020 KB Output is correct
4 Correct 60 ms 127132 KB Output is correct
5 Correct 66 ms 127068 KB Output is correct
6 Correct 58 ms 127156 KB Output is correct
7 Correct 58 ms 127164 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 127124 KB Output is correct
2 Correct 62 ms 127076 KB Output is correct
3 Correct 61 ms 127020 KB Output is correct
4 Correct 60 ms 127132 KB Output is correct
5 Correct 66 ms 127068 KB Output is correct
6 Correct 58 ms 127156 KB Output is correct
7 Correct 58 ms 127164 KB Output is correct
8 Correct 78 ms 127336 KB Output is correct
9 Correct 74 ms 127528 KB Output is correct
10 Correct 69 ms 127520 KB Output is correct
11 Correct 64 ms 127476 KB Output is correct
12 Correct 95 ms 130864 KB Output is correct
13 Correct 105 ms 131148 KB Output is correct
14 Correct 103 ms 131364 KB Output is correct
15 Correct 72 ms 128380 KB Output is correct
16 Correct 69 ms 128352 KB Output is correct
17 Correct 92 ms 130248 KB Output is correct
18 Correct 83 ms 128316 KB Output is correct
19 Correct 113 ms 132496 KB Output is correct
20 Correct 93 ms 130892 KB Output is correct
21 Correct 117 ms 132400 KB Output is correct