| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 968613 | skahl15 | Necklace (Subtask 4) (BOI19_necklace4) | C++17 | 169 ms | 604 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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=j+pi2[n+m-i-j];
Tin=m-Tin;
}
}
}
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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||