Submission #130343

#	Time	Username	Problem	Language	Result	Execution time	Memory
130343		thiago4532	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	1578 ms	400 KiB

necklace

#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int p1 = 1e4 + 7;
const int p2 = 1e9 + 9;
string s, t;
int prefs[3010], preft[3010];

int h(string const& s) {
	int r = 0;

	int p = 1;
	for(int i = 0; i < s.size(); i++) {
		r += (p * (s[i] - 'a' + 1))%p2;
		r %= p2;
		p *= p1;
		p %= p2;
	}
	return r;
}

int power(int a, int b) {
	int r = 1;
	a %= p2;

	while(b) {
		if(b&1) r *= a, r %= p2;

		a *= a;
		a %= p2;
		b >>= 1;
	}
	return r;
}

int h_s(int a, int t) {
	int b = t + a - 1;
	return ((((prefs[b] - (a == 0 ? 0 : prefs[a-1])) * power(p1, a*(p2-2)))%p2)+p2)%p2;
}
int h_t(int a, int t) {
	int  b = t + a - 1;
	return ((((preft[b] - (a == 0 ? 0 : preft[a-1])) * power(p1, a*(p2-2)))%p2)+p2)%p2;
}

	mt19937 gen(random_device{}());
int maximo=1, ini, fim;
void solve(bool rev) {
	uniform_int_distribution<> ri(0, s.size()-1);
	uniform_int_distribution<> rj(0, t.size()-1);
	int porta = (3000*3000)/maximo;

	for(int c=1; c <= porta; c++) {
		int i = ri(gen), j = rj(gen);
		int b_a=0, b_b=0;

		// while(i - a >= 0 && j + a <= t.size() && i + b <= s.size() && j - b >= 0 &&
		// 	s[i - a] == t[j + a - 1] && s[i + b - 1] == t[])		

		for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
			// cout << a << "\n";
			if(h_s(i-a, a) == h_t(j, a))
				b_a = a;
		}
		for(int b = 1; i + b <= s.size() && j - b >= 0; b++) {
			if(h_s(i, b) == h_t(j - b, b)){
				b_b = b;
			}
		}

		// if(b_a != 0 && b_b != 0) cout << b_a << " " << b_b << ": " << b_a + b_b << "\n";
		if(b_a + b_b > maximo) {
			maximo = b_a + b_b;
			ini = i - b_a;
			if(rev) fim = t.size() - (j + b_a);
			else fim = j - b_b;
			porta = (s.size()*t.size())/maximo;
		}
	}
}

int32_t main() {
	cin >> s >> t;
	// cout << "\n" << s << "\n";
	// cout << t << "\n";
	// cout << h(s) << " " << h(t) << "\n";

	int p = 1;
	for(int i = 0; i < s.size(); i++) {
		prefs[i] = ((i==0?0:prefs[i-1]) + ( p * (s[i] - 'a' + 1) )%p2) % p2;
		p *= p1;
		p %= p2;
	}

	p = 1;
	for(int i = 0; i < t.size(); i++) {
		preft[i] = ((i==0?0:preft[i-1]) + ( p * (t[i] - 'a' + 1) )%p2) % p2;
		p *= p1;
		p %= p2;
	}

	// for(int i = 0; i < 5; i++) {
	// 	for(int j = i; j < 5; j++) {
	// 		cout << i << " " << j << ": " << h(s.substr(i, j-i+1)) << " " << h_s(i, j-i+1) << "\n";
	// 	}
	// }

	// cout << h("hia") << " " << h_s(1, 3) << "D\n";

	solve(false);
	reverse(t.begin(), t.end());
	memset(preft, 0, sizeof preft);

	p = 1;
	for(int i = 0; i < t.size(); i++) {
		preft[i] = ((i==0?0:preft[i-1]) + ( p * (t[i] - 'a' + 1) )%p2) % p2;
		p *= p1;
		p %= p2;
	}

	solve(true);

	cout << maximo << "\n" << ini << " " << fim << "\n";
	return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int64_t h(const string&)':
necklace.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp: In function 'void solve(bool)':
necklace.cpp:60:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
                                ~~~~~~^~~~~~~~~~~
necklace.cpp:65:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int b = 1; i + b <= s.size() && j - b >= 0; b++) {
                  ~~~~~~^~~~~~~~~~~
necklace.cpp: In function 'int32_t main()':
necklace.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~

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