제출 #1114750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114750		koukirocks	Match (CEOI16_match)	C++17	100 / 100	47 ms	8784 KiB

match

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63