oj.uz

답안 #130351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130351 2019-07-14T21:53:40 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 + 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{}());
int32_t 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);
	int32_t porta = (s.size()*t.size())/maximo;

	for(int32_t c=1; c <= porta; c++) {
		int32_t i = ri(gen), j = rj(gen);
		int32_t 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(int32_t 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(int32_t 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(int32_t 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(int32_t 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

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:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int32_t a = maximo/2; i - a >= 0 && j + a <= t.size(); a++) {
                                           ~~~~~~^~~~~~~~~~~
necklace.cpp:73:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int32_t b = maximo/2; i + b <= s.size() && j - b >= 0; b++) {
                              ~~~~~~^~~~~~~~~~~
necklace.cpp:79:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int32_t a = maximo - b_b; i - a >= 0 && j + a <= t.size(); a++) {
                                                ~~~~~~^~~~~~~~~~~
necklace.cpp:86:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int32_t 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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 12 ms 9208 KB Output is partially correct
2 Partially correct 12 ms 9208 KB Output is partially correct
3 Correct 22 ms 9208 KB Output is correct
4 Partially correct 25 ms 9208 KB Output is partially correct
5 Partially correct 113 ms 9208 KB Output is partially correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 12 ms 9208 KB Output is partially correct
2 Partially correct 12 ms 9208 KB Output is partially correct
3 Correct 22 ms 9208 KB Output is correct
4 Partially correct 25 ms 9208 KB Output is partially correct
5 Partially correct 113 ms 9208 KB Output is partially correct
6 Partially correct 35 ms 9208 KB Output is partially correct
7 Partially correct 45 ms 9212 KB Output is partially correct
8 Partially correct 281 ms 9336 KB Output is partially correct
9 Partially correct 273 ms 9208 KB Output is partially correct
10 Partially correct 1362 ms 9308 KB Output is partially correct
11 Execution timed out 1577 ms 9208 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 12 ms 9208 KB Output is partially correct
2 Partially correct 12 ms 9208 KB Output is partially correct
3 Correct 22 ms 9208 KB Output is correct
4 Partially correct 25 ms 9208 KB Output is partially correct
5 Partially correct 113 ms 9208 KB Output is partially correct
6 Partially correct 35 ms 9208 KB Output is partially correct
7 Partially correct 45 ms 9212 KB Output is partially correct
8 Partially correct 281 ms 9336 KB Output is partially correct
9 Partially correct 273 ms 9208 KB Output is partially correct
10 Partially correct 1362 ms 9308 KB Output is partially correct
11 Execution timed out 1577 ms 9208 KB Time limit exceeded
12 Halted 0 ms 0 KB -