oj.uz

답안 #476497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476497 2021-09-27T11:45:16 Z hackerbhaiya 원형 문자열 (IZhO13_rowords) C++14
16 / 100
 115 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,1,n)
    {
        f(j,1,m)
        {
            if(a[i]==b[j])
                dp[i][j]=1+dp[i-1][j-1],dir[i][j]=1;
            else
            {
                if(dp[i][j-1]>=dp[i-1][j])
                    dp[i][j]=dp[i][j-1];
                else
                    dp[i][j]=dp[i-1][j],dir[i][j]=2;
            }
        }
    }
}

int cal(int i, int j)
{
    int ans=0;
    while(i>1 && j>1)
    {
        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;
    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+1,m),cur=dif+2;
        f(i,2,n)
        {
            int r=i+dif-1;
            if(r>=n)
                break;
            update(i-1);
            ans=max(ans,cal(cur,m)),cur++;
        }
        reverse(all(tempa));
        a="#"+tempa+tempa;
        init();
        ans=max(ans,cal(dif+1,m));
        f(i,2,n)
        {
            int r=i+dif;
            if(r>=n)
                break;
            update(i);
            ans=max(ans,cal(r,m));
        }
        cout<<ans<<"\n";
    }
}

Subtask #1
16.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 10 ms 1996 KB Output isn't correct
7 Correct 23 ms 16088 KB Output is correct
8 Incorrect 68 ms 16076 KB Output isn't correct
9 Incorrect 72 ms 16096 KB Output isn't correct
10 Incorrect 64 ms 16132 KB Output isn't correct
11 Incorrect 66 ms 17720 KB Output isn't correct
12 Incorrect 52 ms 20556 KB Output isn't correct
13 Incorrect 104 ms 20636 KB Output isn't correct
14 Incorrect 73 ms 18508 KB Output isn't correct
15 Incorrect 87 ms 21964 KB Output isn't correct
16 Incorrect 95 ms 17740 KB Output isn't correct
17 Incorrect 62 ms 13528 KB Output isn't correct
18 Incorrect 91 ms 20932 KB Output isn't correct
19 Incorrect 59 ms 16132 KB Output isn't correct
20 Incorrect 115 ms 18764 KB Output isn't correct
21 Incorrect 34 ms 4532 KB Output isn't correct
22 Correct 47 ms 7628 KB Output is correct
23 Correct 69 ms 10552 KB Output is correct
24 Incorrect 69 ms 11084 KB Output isn't correct
25 Incorrect 85 ms 14792 KB Output isn't correct