oj.uz

Submission #897120

# Submission time Handle Problem Language Result Execution time Memory
897120 2024-01-02T15:02:05 Z pcc Necklace (Subtask 1-3) (BOI19_necklace1) C++14
17 / 85
 1452 ms 984 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 = 1;
		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;
	}
	while(l != r){
		int mid = (l+r+1)>>1;
		if(check(mid))l = mid;
		else r = mid-1;
	}
	check(l);
	cout<<l<<'\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++){
      |                  ~^~~~~~~~~

Subtask #1
5.0 / 25.0

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

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Partially correct 1 ms 348 KB Output is partially correct
3 Correct 1 ms 348 KB Output is correct
4 Partially correct 1 ms 348 KB Output is partially correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 9 ms 440 KB Output is correct
7 Partially correct 8 ms 348 KB Output is partially correct
8 Correct 9 ms 348 KB Output is correct
9 Partially correct 12 ms 640 KB Output is partially correct
10 Partially correct 10 ms 344 KB Output is partially correct
11 Partially correct 8 ms 348 KB Output is partially correct
12 Correct 11 ms 460 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Partially correct 1 ms 348 KB Output is partially correct
3 Correct 1 ms 348 KB Output is correct
4 Partially correct 1 ms 348 KB Output is partially correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 9 ms 440 KB Output is correct
7 Partially correct 8 ms 348 KB Output is partially correct
8 Correct 9 ms 348 KB Output is correct
9 Partially correct 12 ms 640 KB Output is partially correct
10 Partially correct 10 ms 344 KB Output is partially correct
11 Partially correct 8 ms 348 KB Output is partially correct
12 Correct 11 ms 460 KB Output is correct
13 Correct 346 ms 656 KB Output is correct
14 Partially correct 553 ms 656 KB Output is partially correct
15 Correct 296 ms 972 KB Output is correct
16 Correct 592 ms 936 KB Output is correct
17 Partially correct 496 ms 940 KB Output is partially correct
18 Partially correct 308 ms 844 KB Output is partially correct
19 Correct 1452 ms 984 KB Output is correct
20 Correct 898 ms 880 KB Output is correct
21 Correct 520 ms 936 KB Output is correct