oj.uz

Submission #897125

# Submission time Handle Problem Language Result Execution time Memory
897125 2024-01-02T15:08:13 Z pcc Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 652 KB 
#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

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.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 360 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 186 ms 456 KB Output is correct
7 Correct 192 ms 468 KB Output is correct
8 Correct 205 ms 344 KB Output is correct
9 Correct 395 ms 500 KB Output is correct
10 Correct 504 ms 496 KB Output is correct
11 Correct 522 ms 544 KB Output is correct
12 Correct 385 ms 344 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 360 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 186 ms 456 KB Output is correct
7 Correct 192 ms 468 KB Output is correct
8 Correct 205 ms 344 KB Output is correct
9 Correct 395 ms 500 KB Output is correct
10 Correct 504 ms 496 KB Output is correct
11 Correct 522 ms 544 KB Output is correct
12 Correct 385 ms 344 KB Output is correct
13 Execution timed out 1566 ms 652 KB Time limit exceeded
14 Halted 0 ms 0 KB -