Submission #897125

#	Time	Username	Problem	Language	Result	Execution time	Memory
897125		pcc	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	45 / 85	1566 ms	652 KiB

necklace

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 3030;
const ll mod = 712271227;

inline ll pw(ll a,ll b){
	ll re = 1;
	while(b){
		if(b&1)re = re*a%mod;
		b>>=1;
		a = a*a%mod;
	}
	return re;
}
inline ll inv(ll k){
	return pw(k,mod-2);
}
inline ll mad(ll a,ll b){
	 a+= b;
	 return a>=mod?a-mod:a;
}
inline ll mub(ll a,ll b){
	return mad(a,mod-b);
}
inline pll mad(pll a,pll b){
	return make_pair(mad(a.fs,b.fs),mad(a.sc,b.sc));
}
inline pll mub(pll a,pll b){
	return make_pair(mub(a.fs,b.fs),mub(a.sc,b.sc));
}


const pll p = {29,31};
gp_hash_table<ll,int> mp;
string a,b;
int N,M;
const pll ip = {inv(p.fs),inv(p.sc)};
pii ans;
pll ap[mxn],bp[mxn];
string tmp;

inline bool found(string &s,int len){
	pll val = make_pair(0,0);
	pll h = make_pair(1,1);
	for(int i = 0;i<len;i++){
		val.fs = mad(val.fs,h.fs*(s[i]-'a'+1)%mod);
		val.sc = mad(val.sc,h.sc*(s[i]-'a'+1)%mod);
		h.fs = h.fs*p.fs%mod;
		h.sc = h.sc*p.sc%mod;
	}
	if(mp.find(val.fs*mod+val.sc) != mp.end()){
		ans.fs = mp[val.fs*mod+val.sc];
		return true;
	}
	for(int i = len;i<s.size();i++){
		val = mub(val,make_pair(s[i-len]-'a'+1,s[i-len]-'a'+1));
		val.fs = mad(val.fs,h.fs*(s[i]-'a'+1)%mod);
		val.sc = mad(val.sc,h.sc*(s[i]-'a'+1)%mod);
		val.fs = val.fs*ip.fs%mod;
		val.sc = val.sc*ip.sc%mod;
		if(mp.find(val.fs*mod+val.sc) != mp.end()){
			ans.fs = mp[val.fs*mod+val.sc];
			return true;
		}
	}
	return false;
}

inline bool check(int len){
	if(!len){
		ans.fs = ans.sc = 0;
		return true;
	}
	mp.clear();
	pll sum = ap[len];
	mp[sum.fs*mod+sum.sc] = 0;
	pll tp = make_pair(pw(p.fs,len),pw(p.sc,len));
	for(int i = len;i<N;i++){
		sum = mub(sum,make_pair(a[i-len]-'a'+1,a[i-len]-'a'+1));
		sum = mad(sum,make_pair(tp.fs*(a[i]-'a'+1)%mod,tp.sc*(a[i]-'a'+1)%mod));
		sum.fs = sum.fs*ip.fs%mod;
		sum.sc = sum.sc*ip.sc%mod;
		mp[sum.fs*mod+sum.sc] = i-len+1;
	}
	for(int i = 0;i+len<=M;i++){
		tmp = b.substr(i,len);
		tmp += tmp;
		if(found(tmp,len)){
			ans.sc = i;
			return true;
		}
		reverse(tmp.begin(),tmp.end());
		if(found(tmp,len)){
			ans.sc = i;
			return true;
		}
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>a>>b;
	N = a.size(),M = b.size();
	int l = 0,r = N;
	pll tmp = make_pair(1,1);

	for(int i = 0;i<N;i++){
		ap[i+1] = ap[i];
		ap[i+1].fs = mad(ap[i+1].fs,tmp.fs*(a[i]-'a'+1)%mod);
		ap[i+1].sc = mad(ap[i+1].sc,tmp.sc*(a[i]-'a'+1)%mod);
		tmp.fs = tmp.fs*p.fs%mod;
		tmp.sc = tmp.sc*p.sc%mod;
	}
	tmp = make_pair(1,1);
	for(int i = 0;i<M;i++){
		bp[i+1] = bp[i];
		bp[i+1].fs = mad(bp[i+1].fs,tmp.fs*(b[i]-'a'+1)%mod);
		bp[i+1].sc = mad(bp[i+1].sc,tmp.sc*(b[i]-'a'+1)%mod);
		tmp.fs = tmp.fs*p.fs%mod;
		tmp.sc = tmp.sc*p.sc%mod;
	}
	int len = 0;
	for(int i = 1;i<=min(N,M);i++)if(check(i))len = i;
	cout<<len<<'\n'<<ans.fs<<' '<<ans.sc;
}

Compilation message (stderr)

necklace.cpp: In function 'bool found(std::string&, int)':
necklace.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = len;i<s.size();i++){
      |                  ~^~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:115:6: warning: unused variable 'l' [-Wunused-variable]
  115 |  int l = 0,r = N;
      |      ^
necklace.cpp:115:12: warning: unused variable 'r' [-Wunused-variable]
  115 |  int l = 0,r = N;
      |            ^

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