제출 #1207567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207567		Zbyszek99	Match (CEOI16_match)	C++20	0 / 100	0 ms	324 KiB

match

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

string s;
int n;
int arr[100'001];
int jump[100'001][17];
int root_cnt[100'001][26];
char ans[100'001];

void solve(int l, int r)
{
    if(l > r) return;
    int end_v = l+1;
    for(int bit = 16; bit >= 0; bit--)
    {
        if(jump[end_v][bit] <= r)
        {
            end_v = jump[end_v][bit];
        }
    }
    end_v = jump[0][end_v];
    int p = l+1;
    for(int bit = 16; bit >= 0; bit--)
    {
        if(root_cnt[jump[p][bit]][arr[l]] - root_cnt[end_v][arr[l]] > 0)
        {
            p = jump[p][bit];
        }
    }
    ans[l] = '(';
    ans[p] = ')';
    solve(l+1,p-1);
    solve(p+1,r);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    cin >> s;
    int n = siz(s);
    rep(i,n)
    {
        arr[i] = s[i] - 'a';
    }
    arr[n] = 1e9;
    rep(bit,17) jump[n][bit] = n;
    for(int i = n-1; i >= 0; i--)
    {
        if(arr[i] == arr[i+1])
        {
            jump[i][0] = i+2;
        }
        else
        {
            int nxt_cnt = root_cnt[i+1][arr[i]];
            if(nxt_cnt == 0)
            {
                jump[i][0] = i; 
                
            }
            else
            {
                int cur = i+1;
                for(int bit = 16; bit >= 0; bit--)
                {
                    if(root_cnt[jump[cur][bit]][arr[i]] == nxt_cnt)
                    {
                        cur = jump[cur][bit];
                    }
                }
                if(cur != n)
                {
                    jump[i][0] = cur+1;
                }
                else
                {
                    jump[i][0] = i;
                }
            }
        }
        rep2(bit,1,16)
        {
            jump[i][bit] = jump[jump[i][bit-1]][bit-1];
        }
        rep(z,26)
        {
            root_cnt[i][z] = root_cnt[jump[i][0]][z];
        }
        root_cnt[i][arr[i]]++;
    }
    if(jump[jump[0][16]][16] != n)
    {
        cout << "-1\n";
        return 0;
    }
    solve(0,n-1);
    rep(i,n) cout << ans[i];
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63