oj.uz

Submission #589203

# Submission time Handle Problem Language Result Execution time Memory
589203 2022-07-04T10:32:03 Z andrei_boaca Match (CEOI16_match) C++14
100 / 100
 118 ms 133068 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);
    }
    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 57 ms 127056 KB Output is correct
2 Correct 68 ms 127008 KB Output is correct
3 Correct 59 ms 127120 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 127056 KB Output is correct
2 Correct 68 ms 127008 KB Output is correct
3 Correct 59 ms 127120 KB Output is correct
4 Correct 61 ms 127100 KB Output is correct
5 Correct 61 ms 127180 KB Output is correct
6 Correct 72 ms 127156 KB Output is correct
7 Correct 63 ms 127204 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 127056 KB Output is correct
2 Correct 68 ms 127008 KB Output is correct
3 Correct 59 ms 127120 KB Output is correct
4 Correct 61 ms 127100 KB Output is correct
5 Correct 61 ms 127180 KB Output is correct
6 Correct 72 ms 127156 KB Output is correct
7 Correct 63 ms 127204 KB Output is correct
8 Correct 59 ms 127308 KB Output is correct
9 Correct 65 ms 127468 KB Output is correct
10 Correct 62 ms 127568 KB Output is correct
11 Correct 61 ms 127544 KB Output is correct
12 Correct 102 ms 131148 KB Output is correct
13 Correct 108 ms 131660 KB Output is correct
14 Correct 117 ms 131916 KB Output is correct
15 Correct 68 ms 128456 KB Output is correct
16 Correct 72 ms 128424 KB Output is correct
17 Correct 93 ms 130656 KB Output is correct
18 Correct 76 ms 128328 KB Output is correct
19 Correct 117 ms 133068 KB Output is correct
20 Correct 99 ms 131312 KB Output is correct
21 Correct 118 ms 133064 KB Output is correct