Submission #130347

# Submission time Handle Problem Language Result Execution time Memory
130347 2019-07-14T21:41:44 Z thiago4532 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
5 / 85
1500 ms 9336 KB
#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;
}

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 = (max(s.size(), t.size())*max(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;
		}
		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 = (max(s.size(), t.size())*max(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

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:72:35: 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:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 9208 KB Output is partially correct
2 Partially correct 11 ms 9336 KB Output is partially correct
3 Partially correct 20 ms 9208 KB Output is partially correct
4 Correct 22 ms 9208 KB Output is correct
5 Partially correct 95 ms 9208 KB Output is partially correct
# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 9208 KB Output is partially correct
2 Partially correct 11 ms 9336 KB Output is partially correct
3 Partially correct 20 ms 9208 KB Output is partially correct
4 Correct 22 ms 9208 KB Output is correct
5 Partially correct 95 ms 9208 KB Output is partially correct
6 Partially correct 22 ms 9208 KB Output is partially correct
7 Partially correct 29 ms 9208 KB Output is partially correct
8 Partially correct 258 ms 9212 KB Output is partially correct
9 Correct 208 ms 9208 KB Output is correct
10 Partially correct 992 ms 9248 KB Output is partially correct
11 Execution timed out 1574 ms 9208 KB Time limit exceeded
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 9208 KB Output is partially correct
2 Partially correct 11 ms 9336 KB Output is partially correct
3 Partially correct 20 ms 9208 KB Output is partially correct
4 Correct 22 ms 9208 KB Output is correct
5 Partially correct 95 ms 9208 KB Output is partially correct
6 Partially correct 22 ms 9208 KB Output is partially correct
7 Partially correct 29 ms 9208 KB Output is partially correct
8 Partially correct 258 ms 9212 KB Output is partially correct
9 Correct 208 ms 9208 KB Output is correct
10 Partially correct 992 ms 9248 KB Output is partially correct
11 Execution timed out 1574 ms 9208 KB Time limit exceeded
12 Halted 0 ms 0 KB -