oj.uz

Submission #589200

# Submission time Handle Problem Language Result Execution time Memory
589200 2022-07-04T10:30:01 Z andrei_boaca Match (CEOI16_match) C++14
100 / 100
 126 ms 133988 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;
vector<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]].push_back(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;
            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.insert(poz);
        }
        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 56 ms 127052 KB Output is correct
2 Correct 60 ms 127044 KB Output is correct
3 Correct 66 ms 127100 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 127052 KB Output is correct
2 Correct 60 ms 127044 KB Output is correct
3 Correct 66 ms 127100 KB Output is correct
4 Correct 57 ms 127164 KB Output is correct
5 Correct 57 ms 127192 KB Output is correct
6 Correct 57 ms 127180 KB Output is correct
7 Correct 58 ms 127180 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 127052 KB Output is correct
2 Correct 60 ms 127044 KB Output is correct
3 Correct 66 ms 127100 KB Output is correct
4 Correct 57 ms 127164 KB Output is correct
5 Correct 57 ms 127192 KB Output is correct
6 Correct 57 ms 127180 KB Output is correct
7 Correct 58 ms 127180 KB Output is correct
8 Correct 73 ms 127372 KB Output is correct
9 Correct 63 ms 127560 KB Output is correct
10 Correct 66 ms 127636 KB Output is correct
11 Correct 62 ms 127712 KB Output is correct
12 Correct 98 ms 131872 KB Output is correct
13 Correct 104 ms 132244 KB Output is correct
14 Correct 116 ms 132664 KB Output is correct
15 Correct 74 ms 129536 KB Output is correct
16 Correct 75 ms 129552 KB Output is correct
17 Correct 97 ms 131920 KB Output is correct
18 Correct 77 ms 128900 KB Output is correct
19 Correct 122 ms 133760 KB Output is correct
20 Correct 98 ms 132172 KB Output is correct
21 Correct 126 ms 133988 KB Output is correct