Submission #720973

#	Time	Username	Problem	Language	Result	Execution time	Memory
720973		n0sk1ll	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	0 / 85	14 ms	320 KiB

necklace

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

int power(int a, int n, int mod)
{
    li c=1;
    while (n)
    {
        if (n&1) (c*=a)%=mod;
        a=(li)a*a%mod,n>>=1;
    }
    return c;
}

struct hashing
{
    int p,mod;
    int pre[3005]; //normal order
    int suf[3005]; //reverse order
    int ps[3005],pi[3005]; //stepeni i inverzi
    int w[26]; //random weight svakog slova

    void setprost(int sta)
    {
        p=sta;
    }

    void setmod(int sta)
    {
        mod=sta;
    }

    void build(string &s, int n)
    {
        mt19937 rng(time(NULL));
        ff(i,0,26) w[i]=rng()%mod;

        fff(i,1,n) pre[i]=((li)pre[i-1]*p%mod+w[s[i-1]-'a'])%mod;
        bfff(i,1,n) suf[i]=((li)suf[i+1]*p%mod+w[s[i-1]-'a'])%mod;

        ps[0]=1,pi[0]=1;
        fff(i,1,n) ps[i]=(li)ps[i-1]*p%mod;
        pi[1]=power(p,mod-2,mod);
        fff(i,2,n) pi[i]=(li)pi[i-1]*pi[1]%mod;
    }

    int Hash(int l, int r) //normal order: left to right
    {
        return (pre[r]+mod-(li)pre[l-1]*ps[r-l+1]%mod)%mod;
    }

    int rHash(int l, int r) //reverse order: right to left
    {
        return (suf[l]+mod-(li)suf[r+1]*ps[r-l+1]%mod)%mod;
    }
} A,B;

bool imalijednakih(vector<int> &Ahashovi, vector<int> &Bhashovi)
{
    sort(all(Bhashovi));
    for (auto it : Ahashovi) if (find(all(Bhashovi),it)!=Bhashovi.end()) return true;
    return false;
}

int dp1[2][3005]; //cur i preth; oznacava odakle pocinje lex max
bool smer1[2][3005]; //da li citam udesno?

int dp2[2][3005];
bool smer2[2][3005];

string a,b;
int MajorHash(int l, int r, int i, bool s, int dulj)
{
    return 0; ///function yet to be implemented
    if (s)
    {
        //if (dulj<=(r-i+1)) return Hash(i,i+dulj-1);

    }
    else
    {

    }
}

bool manji(string &s,   int l1, int r1, int i1, bool s1,    int l2, int r2, int i2, bool s2)
{
    assert(r1-l1 == r2-l2); //inace ne znam sta radim sa zivotom
    int l=0,r=(r1-l1+1); //nabadamo duzinu
    while (r-l>1)
    {
        int mid=(l+r)/2;
        if (MajorHash(l1,r1,i1,s1,mid)==MajorHash(l2,r2,i2,s2,mid)) l=mid;
        else r=mid;
    }

    int gde1=(i1+r);
    if (gde1>r1) gde1-=(r1-l1+1);

    int gde2=(i2+r);
    if (gde2>r2) gde2-=(r2-l2+1);

    return s[gde1-1]<s[gde2-1];
}

int main()
{
    FAST;

    cin>>a>>b;
    int n=(int)a.size(),m=(int)b.size();

    A.setmod(1000000007),A.setprost(1000003);
    B.setmod(1000000007),B.setprost(1000003);
    A.build(a,n),B.build(b,m);

    int ans=0;
    bool cur=0;

    fff(i,1,n) dp1[cur][i]=i,smer1[cur][i]=1;
    fff(i,1,n) dp2[cur][i]=i,smer2[cur][i]=1;

    /*fff(k,2,n)
    {
        cur=!cur;
        fff(i,k,n) //[i-k+1,i]
        {
            if (manji(a,   i-k+1,i-1,dp[!cur][i-k+1],smer[!cur][i-k+1],  i-k+2,i,dp[!cur][i-k+2],smer[!cur][i-k+2]))
                dp[cur][i-k+1]=dp[!cur][i-k+1],smer[cur][i-k+1]=smer[!cur][i-k+1];
            else dp[cur][i-k+1]=dp[!cur][i-k+2],smer[cur][i-k+1]=smer[!cur][i-k+2];
        }
    }*/

    if (n>400 || m>400) return 0; ///DELETE THIS LATER

    fff(k,1,min(n,m))
    {
        vector<int> aha,bha;
        fff(i,1,n-k+1)
        {
            fff(j,i,i+k-1)
            {
                int th=((li)A.Hash(j,i+k-1)*A.ps[j-i]+A.Hash(i,j-1))%A.mod;
                int rh=((li)A.rHash(i,j-1)*A.ps[i+k-j]+A.rHash(j,i+k-1))%A.mod;
                aha.pb(th),aha.pb(rh);
            }
        }
        fff(i,1,m-k+1)
        {
            bha.pb(B.Hash(i,i+k-1));
        }
        if (imalijednakih(aha,bha)) ans=k;
    }

    cout<<ans<<"\n";
}

//Note to self: Check for overflow

/*



*/

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40