oj.uz

Submission #968612

# Submission time Handle Problem Language Result Execution time Memory
968612 2024-04-23T17:37:19 Z skahl15 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 159 ms 860 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];
      |    ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 3 ms 524 KB Output is correct
11 Correct 2 ms 356 KB Output is correct
12 Correct 4 ms 348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 3 ms 524 KB Output is correct
11 Correct 2 ms 356 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 130 ms 604 KB Output is correct
14 Correct 96 ms 588 KB Output is correct
15 Correct 159 ms 604 KB Output is correct
16 Correct 138 ms 860 KB Output is correct
17 Correct 79 ms 612 KB Output is correct
18 Correct 102 ms 604 KB Output is correct
19 Correct 101 ms 600 KB Output is correct
20 Correct 122 ms 840 KB Output is correct
21 Correct 121 ms 604 KB Output is correct