Submission #130350

#	Time	Username	Problem	Language	Result	Execution time	Memory
130350		thiago4532	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	5 / 85	1322 ms	9308 KiB

necklace

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

using namespace std;
const int p1 = 1e4 + 7;
const int p2 = 1e9 + 7;
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 /= 2;
	}
	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;
}

bool mark[3010][3010];

mt19937 gen(random_device{}());
int maximo=1, ini, fim;
void solve(bool rev) {
	memset(mark, 0, sizeof mark);

	uniform_int_distribution<> ri(0, s.size()-1);
	uniform_int_distribution<> rj(0, t.size()-1);
	int porta = (s.size()*t.size())/maximo;

	for(int c=1; c <= porta; c++) {
		int i = ri(gen), j = rj(gen);
		int b_a=0, b_b=0;
		// if(mark[i][j]) {
		// 	c--;
		// 	continue;
		// }

		// 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 = maximo/2; i - a >= 0 && j + a <= t.size(); a++) {
			if(h_s(i-a, a) == h_t(j, a))
				b_a = a;
		}
		if(b_a == 0){
			for(int b = maximo/2; i + b <= s.size() && j - b >= 0; b++) {
				if(h_s(i, b) == h_t(j - b, b)){
					b_b = b;
				}
			}
			if(b_b == 0) continue;
			for(int a = maximo - b_b; i - a >= 0 && j + a <= t.size(); a++) {
				if(h_s(i-a, a) == h_t(j, a))
					b_a = a;
			}
			if(b_a == 0) continue;

		}else{
			for(int b = maximo - b_a; i + b <= s.size() && j - b >= 0; b++) {
				if(h_s(i, b) == h_t(j - b, b)){
					b_b = b;
				}
			}
		}
		
		if(b_b == 0)
			continue;

		// 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:68:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int a = maximo/2; i - a >= 0 && j + a <= t.size(); a++) {
                                       ~~~~~~^~~~~~~~~~~
necklace.cpp:73:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int b = maximo/2; i + b <= s.size() && j - b >= 0; b++) {
                          ~~~~~~^~~~~~~~~~~
necklace.cpp:79:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = maximo - b_b; i - a >= 0 && j + a <= t.size(); a++) {
                                            ~~~~~~^~~~~~~~~~~
necklace.cpp:86:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int b = maximo - b_a; i + b <= s.size() && j - b >= 0; b++) {
                              ~~~~~~^~~~~~~~~~~
necklace.cpp: In function 'int32_t main()':
necklace.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:140:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~

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