oj.uz

Submission #476501

# Submission time Handle Problem Language Result Execution time Memory
476501 2021-09-27T11:56:45 Z hackerbhaiya Round words (IZhO13_rowords) C++14
36 / 100
 100 ms 21960 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>0 && j>0)
    {
        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();
        // cout<<dp[9][2]<<"\n";
        // for(int i=0;i<10;i++)
        // {
        //     for(int j=0;j<m;j++)
        //         cout<<dir[i][j]<<" ";
        //     cout<<"\n";
        // }
        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)),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++;
        }
        cout<<ans<<"\n";
    }
}

Subtask #1
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 9 ms 2036 KB Output is correct
7 Correct 22 ms 16068 KB Output is correct
8 Incorrect 68 ms 16140 KB Output isn't correct
9 Incorrect 74 ms 16076 KB Output isn't correct
10 Incorrect 61 ms 16092 KB Output isn't correct
11 Incorrect 63 ms 17612 KB Output isn't correct
12 Correct 55 ms 20648 KB Output is correct
13 Incorrect 100 ms 20648 KB Output isn't correct
14 Incorrect 78 ms 18504 KB Output isn't correct
15 Incorrect 88 ms 21960 KB Output isn't correct
16 Incorrect 85 ms 17768 KB Output isn't correct
17 Incorrect 64 ms 13536 KB Output isn't correct
18 Incorrect 94 ms 21004 KB Output isn't correct
19 Incorrect 55 ms 16076 KB Output isn't correct
20 Incorrect 96 ms 18764 KB Output isn't correct
21 Correct 31 ms 4556 KB Output is correct
22 Incorrect 48 ms 7680 KB Output isn't correct
23 Incorrect 57 ms 10444 KB Output isn't correct
24 Incorrect 67 ms 11084 KB Output isn't correct
25 Incorrect 87 ms 14716 KB Output isn't correct