oj.uz

Submission #1114750

# Submission time Handle Problem Language Result Execution time Memory
1114750 2024-11-19T14:31:28 Z koukirocks Match (CEOI16_match) C++17
100 / 100
 47 ms 8784 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

ll pw(ll a,ll b) {
    ll ans=1;
    ll now=a;
    while (b) {
        if (b&1) {
            ans*=now;
            ans%=P;
        }
        now*=now;
        now%=P;
        b>>=1;
    }
    return ans;
}

struct Hash {
    vector<int> stk;
    ll x;
    ll curr,nowx,inv;
    Hash(ll x):x(x),curr(0),nowx(1),inv(pw(x,P-2)) {}
    ll add(ll v) {
        // cout<<v<<" v\n"<<flush;
        // cout<<nowx<<" nowx\n";
        // for (int i:stk) cout<<i<<" stk\n"<<flush;
        if (!stk.empty() and stk.back()==v) {
            curr-=nowx*v%P;
            curr=(curr%P+P)%P;
            nowx=nowx*inv%P;
            stk.pop_back();
        } else {
            nowx=nowx*x%P;
            curr+=nowx*v%P;
            curr%=P;
            stk.push_back(v);
        }
        return curr;
    }
};

void cal(vector<int> &ans,int l,int r,map<int,vector<int>> &pos,vector<int> &hv) {
    // cout<<l<<" "<<r<<"\n";
    if (l>r) return;
    auto it=lower_bound(all(pos[hv[l]]),r);
    int pp=*prev(it)+1;
    ans[l]=1;
    ans[pp]=2;
    cal(ans,l+1,pp-1,pos,hv);
    cal(ans,pp+1,r,pos,hv);
}

int main() {
    speed;
    string s;
    cin>>s;
    Hash st(83);
    map<int,vector<int>> pos;
    int n=s.size();
    vector<int> hv(n);
    for (int i=0;i<n;i++) {
        hv[i]=st.add(s[i]-'a'+1);
        pos[hv[i]].push_back(i);
        // cout<<i<<"\n"<<flush;
    }
    // for (auto [a,v]:pos) {
    //     cout<<a<<" : ";
    //     for (auto i:v) cout<<i<<" ";
    //     cout<<"\n";
    // }
    if (!st.stk.empty()) {
        cout<<"-1\n";
        return 0;
    }
    vector<int> ans(n);
    cal(ans,0,n-1,pos,hv);
    for (int i=0;i<n;i++) {
        cout<<(ans[i]==1?'(':')');
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 456 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 3 ms 1036 KB Output is correct
11 Correct 3 ms 1104 KB Output is correct
12 Correct 28 ms 5968 KB Output is correct
13 Correct 36 ms 6400 KB Output is correct
14 Correct 32 ms 7240 KB Output is correct
15 Correct 13 ms 5200 KB Output is correct
16 Correct 11 ms 5200 KB Output is correct
17 Correct 29 ms 7248 KB Output is correct
18 Correct 12 ms 3320 KB Output is correct
19 Correct 46 ms 8008 KB Output is correct
20 Correct 29 ms 6224 KB Output is correct
21 Correct 47 ms 8784 KB Output is correct