oj.uz

답안 #130341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130341 2019-07-14T21:05:13 Z thiago4532 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 504 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;
}

int maximo, ini, fim;
void solve(bool rev) {
	for(int i = 0; i < s.size(); i++) {
		for(int j = 0; j < t.size(); j++) { 
			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)){
					if(s.substr(i, b) != t.substr(j - b, b)) {
						cout << s.substr(i, b) << " " << t.substr(j - b,  b) << "\n";
						cout << h(s.substr(i, b)) << " " << h(t.substr(j - b,  b)) << "\n";

					}
					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;
			}
		}
	}
}

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:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < t.size(); j++) { 
                  ~~^~~~~~~~~~
necklace.cpp:55:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
                                 ~~~~~~^~~~~~~~~~~
necklace.cpp:60:25: 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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 564 ms 376 KB Output is correct
2 Correct 544 ms 376 KB Output is correct
3 Correct 350 ms 380 KB Output is correct
4 Correct 381 ms 504 KB Output is correct
5 Correct 488 ms 400 KB Output is correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 564 ms 376 KB Output is correct
2 Correct 544 ms 376 KB Output is correct
3 Correct 350 ms 380 KB Output is correct
4 Correct 381 ms 504 KB Output is correct
5 Correct 488 ms 400 KB Output is correct
6 Execution timed out 1552 ms 372 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 564 ms 376 KB Output is correct
2 Correct 544 ms 376 KB Output is correct
3 Correct 350 ms 380 KB Output is correct
4 Correct 381 ms 504 KB Output is correct
5 Correct 488 ms 400 KB Output is correct
6 Execution timed out 1552 ms 372 KB Time limit exceeded
7 Halted 0 ms 0 KB -