Submission #156350

#	Time	Username	Problem	Language	Result	Execution time	Memory
156350		ryansee	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	1275 ms	504 KiB

necklace

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }

#define ll long long int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (3006)
string A[2];
const ll mod=1e9+9;
const ll base=37;
ll pw[MAXN];
ll s[2], ans=0, l[2], r[2], n[2]; bool rev;
void solve() {
	auto start = chrono::high_resolution_clock::now();
	while(1) {
		auto finish=chrono::high_resolution_clock::now();
		chrono::duration<ld> elapsed=finish-start;
		if(elapsed.count() > (ld)0.65) break;
		FOR(i,0,1) {
			l[i]=rand(0, n[i]-1);
			r[i]=l[i];
		}
		if(A[0][l[0]]!=A[1][l[1]] || 2*(min(l[0],l[1])+min(n[0]-r[0]-1, n[1]-r[1]-1)) <= ans) continue;
		while(min(l[0],l[1]) > 0 && A[0][l[0]-1]==A[1][l[1]-1]) --l[0], --l[1];
		while(r[0]+1 < n[0] && r[1]+1 < n[1] && A[0][r[0]+1]==A[1][r[1]+1]) ++r[0], ++r[1];
		ll len=r[0]-l[0]+1;
		if(2*len <= ans) continue;
		if(len > ans) {
			ans=len;
			tie(s[0],s[1])=tie(l[0],l[1]);
			if(rev) s[1]=n[1]-r[1]-1;
		}
		FOR(i,0,1) {
			vector<ll> hash(2, 0);
			FOR(j,1,len) {
				if(r[i] + j >= n[i] || l[!i] - j < 0) break;
				hash[i]+=(ll)(A[i][r[i]+j]-'a')*pw[j-1]%mod;
				hash[i]%=mod;
				hash[!i]*=base, hash[!i]%=mod;
				hash[!i]+=(ll)(A[!i][l[!i]-j]-'a'), hash[!i]%=mod;
				if(hash[i] == hash[!i] && len+j > ans){
					ans=len+j;
					s[0]=l[i];
					s[1]=l[!i]-j;
					if(i) swap(s[0],s[1]);
					if(rev) s[1]=n[1]-r[1]-(i?j:0)-1;
					// if(s[1] == 6 && rev) cerr<<n[1]<<' '<<l[1]<<' '<<r[1]<<' '<<i<<' '<<j<<'\n';
				}
			}
		}
	}
}
int main()
{
	FAST
	cin>>A[0]>>A[1];
	n[0]=A[0].size(), n[1]=A[1].size();
	pw[0]=1; FOR(i,1,MAXN-1) pw[i]=pw[i-1]*base%mod;
	solve();
	reverse(all(A[1]));rev=1;
	solve();
	assert(ans), cout<<ans<<'\n'<<s[0]<<' '<<s[1]<<'\n';
}

• Subtask 1: 15 / 15