Submission #968610

# Submission time Handle Problem Language Result Execution time Memory
968610 2024-04-23T17:33:57 Z skahl15 Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
168 ms 844 KB
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <vector>
#include <set>
#include <cstdio>
#define ll long long
#define se second
#define f first
#define ld long double
#define pb push_back
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
/// if a & m are relatively prime, then (a^(n))%m=(a^(n%phi(m)))%m
/// if not relatively prime, then (a^(n))%m=(a^(phi(m)+n%phi(m)))%m
//ld pi=3.14159265358979323846;
ll oo=1e9+7;
mt19937_64 rnd(98275314);
ll mul(ll x,ll y)
{
    return ((x%oo)*(y%oo))%oo;
}
ll add(ll x,ll y)
{
    return ((x%oo)+(y%oo))%oo;
}
ll sub(ll x,ll y)
{
    return ((x%oo)-(y%oo)+oo+oo)%oo;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
///                XOR set (XOR basis technique) A.K.A :  Gaussian Elimination MOD 2

struct XOR_set
{

    const int N = 62; /// log2 of the maximum possibly inserted mask

    /// base mask of each bit
    ll basis[63];

    XOR_set()
    {
        memset(basis, 0, sizeof(basis));
    }

    void clear()
    {
        memset(basis, 0, sizeof(basis));
    }

    int size()
    {
        int sz = 0;
        for(int i = 0 ; i <= N ; i++)
        {
            sz += (basis[i] > 0);
        }
        return sz;
    }

    /// assigning another set to the current one
    XOR_set operator =(const XOR_set &other)
    {
        for(int i = 0 ; i <= N ; i++)
        {
            basis[i] = other.basis[i];
        }
        return *this;
    }

    /// merging two sets
    XOR_set operator +(const XOR_set &other)
    {
        XOR_set res;
        res = other;
        for(int i = 0 ; i <= N ; i++)
        {
            res.insert(basis[i]);
        }
        return res;
    }

    /// merging another set with the current one
    XOR_set operator +=(const XOR_set &other)
    {
        for(int i = 0 ; i <= N ; i++)
        {
            insert(other.basis[i]);
        }
        return *this;
    }

    /// insert a mask in the set
    void insert(long long mask)
    {
        for(int i = N ; i >= 0 ; i--)
        {
            if(!(mask & (1LL << i))) continue;
            if(!basis[i])
            {
                basis[i] = mask;
                return;
            }
            mask ^= basis[i];
        }
    }

    /// insert a set in the set
    void insert(const XOR_set &other)
    {
        for(int i = 0 ; i <= N ; i++)
        {
            insert(other.basis[i]);
        }
    }

    /// -1 if the mask isn't in the set
    /// cnt if the mask can be created from cnt basis masks
    int find(long long mask)
    {
        int cnt = 0;
        for(int i = N ; i >= 0 ; i--)
        {
            if(mask & (1LL << i))
            {
                mask ^= basis[i];
            }
            cnt += (basis[i] > 0);
        }
        return (mask ? -1 : cnt);
    }

    /// 1 if the mask can be created from subset XOR's
    /// 0 if not
    bool count(long long mask)
    {
        for(int i = N ; i >= 0 ; i--)
        {
            if(mask & (1LL << i))
            {
                mask ^= basis[i];
            }
        }
        return (mask == 0);
    }

    /// maximum subset XOR in the set
    long long get_max(long long mask = 0)
    {
        for(int i = N ; i >= 0 ; i--)
        {
            if((mask ^ basis[i]) > mask)
            {
                mask ^= basis[i];
            }
        }
        return mask;
    }
    /// the k-- is to make k stand for how many numbers we're going to skip
    long long get_kth_greatest(long long k)
    {
        k--;
        if(k==0)return this->get_max();
        long long ret=0;
        long long po=1;
        po=(1<<(this->size()-1));
        for(int i=N; i>=0; i--)
        {
            if(basis[i]==0)continue;
            if(k>=po)
            {
                k-=po;
                po/=2;
                if((ret^basis[i])<ret)ret^=basis[i];
            }
            else
            {
                po/=2;
                if((ret^basis[i])>ret)ret^=basis[i];
            }
        }
        return ret;
    }
};

ll fast_pow(ll x,ll y)
{
    ll ret=1;
    while(y)
    {
        if(y&1)ret=mul(ret,x);
        x=mul(x,x);
        y>>=1;
    }
    return ret;
}
ll fact[100];
ll inv[100];
ll calculate_inverse(ll x)
{
    return fast_pow(x,oo-2);
}
void factorial()
{
    fact[0]=1;
    for(int i=1; i<=300000; i++)
    {
        fact[i]=mul(fact[i-1],i);
    }
    inv[300000]=calculate_inverse(fact[300000]);
    for(int i=300000; i>0; i--)inv[i-1]=mul(inv[i],i);
}
ll nCr(ll n,ll r)
{
    if(r<0)return 0;
    ll ret=1;
    ret=fact[n];
    ret=mul(ret,inv[r]);
    ret=mul(ret,inv[n-r]);
    //ret=mul(ret,calculate_inverse(fact[r]));
    //ret=mul(ret,calculate_inverse(fact[n-r]));
    return ret;
}
ll gcd(ll x,ll y)
{
    if(x<y)swap(x,y);
    if(y==0)return x;
    return gcd(y,x%y);
}
ll phi(ll x)
{
    ll ans=x;
    for(ll i=2; i*i<=x; i++)
    {
        if(x%i!=0)continue;
        while(x%i==0)x/=i;
        ans-=ans/i;
    }
    if(x!=1)
    {
        ans-=ans/x;
    }
    return ans;
}
ll lcm(ll a,ll b)
{
    ll ret=a/gcd(a,b);
    return ret*b;
}
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        y=0;
        x=1;
        return a;
    }
    ll x1,y1;
    ll g=ex_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}
int get_set_bits(ll x)
{
    return __builtin_popcount(x);
}
int n,m,k;
int pi1[6060],pi2[6060];
void kmp(string s,int *pi)
{
    pi[0]=0;
    for(int i=1;i<s.size();i++)
    {
        int j=pi[i-1];
        while(j>0&&s[j]!=s[i])j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
}
void test_case()
{
    string s,t;
    cin>>s>>t;
    int ans,Sin,Tin;
    ans=Sin=Tin=0;
    n=s.size();
    m=t.size();
    string t1,t2;
    t1=t;
    t2=t;
    reverse(t2.begin(),t2.end());
    for(int i=0;i<n;i++)
    {
        string s1,s2;
        s1=s.substr(0,i);
        s2=s.substr(i,n-i);
        reverse(s1.begin(),s1.end());
        kmp(s1+"#"+t1,pi1);
        kmp(s2+"#"+t2,pi2);
        for(int j=1;j<=m;j++)
        {
            if(pi1[i+j]+pi2[n+m-i-j]>ans)
            {
                ans=pi1[i+j]+pi2[n+m-i-j];
                Sin=i-pi1[i+j];
                Tin=j-pi1[i+j];
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        string s1,s2;
        s1=s.substr(0,i);
        s2=s.substr(i,n-i);
        reverse(s1.begin(),s1.end());
        kmp(s1+"#"+t2,pi1);
        kmp(s2+"#"+t1,pi2);
        for(int j=1;j<=m;j++)
        {
            if(pi1[i+j]+pi2[n+m-i-j]>ans)
            {
                ans=pi1[i+j]+pi2[n+m-i-j];
                Sin=i-pi1[i+j];
                Tin=m-j-pi2[n+m-i-j];
            }
        }
    }
    cout<<ans<<'\n';
    cout<<Sin<<" "<<Tin;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*freopen("meta_game_input.txt","r",stdin);
    freopen("solution.txt","w",stdout);*/
    int t=1;
    //cin>>t;
    while(t--)
    {
        test_case();
    }
    return 0;
}

Compilation message

necklace.cpp: In function 'void kmp(std::string, int*)':
necklace.cpp:276:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  276 |     for(int i=1;i<s.size();i++)
      |                 ~^~~~~~~~~
necklace.cpp: In function 'void factorial()':
necklace.cpp:211:20: warning: iteration 100 invokes undefined behavior [-Waggressive-loop-optimizations]
  211 |         fact[i]=mul(fact[i-1],i);
      |                 ~~~^~~~~~~~~~~~~
necklace.cpp:209:19: note: within this loop
  209 |     for(int i=1; i<=300000; i++)
      |                  ~^~~~~~~~
necklace.cpp:213:34: warning: array subscript 300000 is above array bounds of 'long long int [100]' [-Warray-bounds]
  213 |     inv[300000]=calculate_inverse(fact[300000]);
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
necklace.cpp:200:4: note: while referencing 'fact'
  200 | ll fact[100];
      |    ^~~~
necklace.cpp:213:15: warning: array subscript 300000 is above array bounds of 'long long int [100]' [-Warray-bounds]
  213 |     inv[300000]=calculate_inverse(fact[300000]);
      |     ~~~~~~~~~~^
necklace.cpp:201:4: note: while referencing 'inv'
  201 | ll inv[100];
      |    ^~~
# Verdict Execution time Memory Grader output
1 Correct 157 ms 592 KB Output is correct
2 Correct 100 ms 600 KB Output is correct
3 Correct 168 ms 844 KB Output is correct
4 Correct 110 ms 588 KB Output is correct
5 Correct 78 ms 596 KB Output is correct
6 Correct 89 ms 604 KB Output is correct
7 Correct 101 ms 608 KB Output is correct
8 Correct 123 ms 604 KB Output is correct
9 Correct 124 ms 596 KB Output is correct