oj.uz

답안 #476513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476513 2021-09-27T12:55:42 Z hackerbhaiya 원형 문자열 (IZhO13_rowords) C++14
88 / 100
 109 ms 21964 KB 
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll long long
// #define ll int
#define f(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
// ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

vector<vector<int> > dp,dir;
string a,b;
int n,m;

void init()
{
    f(i,0,n)
    {
        f(j,0,m)
            dp[i][j]=dir[i][j]=0;
    }
    f(i,1,n)
    {
        f(j,1,m)
        {
            if(a[i]==b[j])
                dp[i][j]=1+dp[i-1][j-1],dir[i][j]=1;
            if(dp[i][j-1]>=dp[i-1][j] && dp[i][j]<=dp[i][j-1])
                dp[i][j]=dp[i][j-1],dir[i][j]=0;
            if(dp[i][j]<dp[i-1][j])
                dp[i][j]=dp[i-1][j],dir[i][j]=2;
        }
    }
}

int cal(int i, int j)
{
    int ans=0;
    while(i>0 && j>0)
    {
        if(i<0 || j<0)
            return ans;
        if(dir[i][j]==1)
            ans++,i--,j--;
        else if(dir[i][j]==0)
            j--;
        else
            i--;
    }
    return ans;
}

void update(int id)
{
    int i=id,j=1;
    while(j<m && dir[i][j]!=1)
        j++;
    if(j>=m)
        return;
    dir[i][j]=0;
    if(j==1)
        return;
    while(i<n-1 && j<m-1)
    {
        if(dir[i+1][j]==2)
            i++,dir[i][j]=0;
        else if(dir[i+1][j+1]==1)
            i++,j++,dir[i][j]=0;
        else
            j++;
    }
    while(i<n && j<m)
    {
        if(dir[i+1][j]==2)
            i++,dir[i][j]=0;
        else
            break;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    f(i,1,z+1)
    {
        //cout<<"Case #"<<i<<": ";
        cin>>a>>b;
        string tempa=a,tempb=b;
        int dif=sz(tempa);
        a="#"+tempa+tempa,b="$"+tempb;
        n=sz(a),m=sz(b);
        dp.rz(n,vector<int> (m)),dir.rz(n+1,vector<int> (m+1));
        init();
        int ans=cal(dif,m-1),cur=dif+1;
        f(i,2,n)
        {
            if(cur>=n)
                break;
            update(i-1);
            ans=max(ans,cal(cur,m-1)),cur++;
        }
        reverse(all(tempa));
        a="#"+tempa+tempa;
        init();
        ans=max(ans,cal(dif,m-1)),cur=dif+1;
        f(i,2,n)
        {
            if(cur>=n)
                break;
            update(i-1);
            ans=max(ans,cal(cur,m-1)),cur++;
        }
        cout<<ans<<"\n";
    }
}

Subtask #1
88.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 10 ms 2036 KB Output is correct
7 Correct 27 ms 16076 KB Output is correct
8 Incorrect 72 ms 16124 KB Output isn't correct
9 Correct 85 ms 16076 KB Output is correct
10 Correct 68 ms 16128 KB Output is correct
11 Correct 94 ms 17708 KB Output is correct
12 Correct 48 ms 20556 KB Output is correct
13 Correct 109 ms 20656 KB Output is correct
14 Correct 86 ms 18380 KB Output is correct
15 Incorrect 98 ms 21964 KB Output isn't correct
16 Incorrect 92 ms 17768 KB Output isn't correct
17 Correct 73 ms 13516 KB Output is correct
18 Correct 100 ms 21032 KB Output is correct
19 Correct 62 ms 16076 KB Output is correct
20 Correct 107 ms 18836 KB Output is correct
21 Correct 32 ms 4556 KB Output is correct
22 Correct 51 ms 7704 KB Output is correct
23 Correct 69 ms 10508 KB Output is correct
24 Correct 76 ms 11084 KB Output is correct
25 Correct 99 ms 14776 KB Output is correct