oj.uz

답안 #130352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130352 2019-07-14T21:54:21 Z thiago4532 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
5 / 85
 1500 ms 9332 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;
		}
		mark[i][j] = true;

		// 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:69: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:74: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:80: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:87: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:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:122:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:141: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 Partially correct 22 ms 9208 KB Output is partially correct
4 Partially correct 25 ms 9212 KB Output is partially correct
5 Correct 83 ms 9208 KB Output is 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 Partially correct 22 ms 9208 KB Output is partially correct
4 Partially correct 25 ms 9212 KB Output is partially correct
5 Correct 83 ms 9208 KB Output is correct
6 Partially correct 35 ms 9208 KB Output is partially correct
7 Partially correct 47 ms 9208 KB Output is partially correct
8 Partially correct 272 ms 9244 KB Output is partially correct
9 Partially correct 272 ms 9332 KB Output is partially correct
10 Partially correct 1289 ms 9244 KB Output is partially correct
11 Execution timed out 1569 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 Partially correct 22 ms 9208 KB Output is partially correct
4 Partially correct 25 ms 9212 KB Output is partially correct
5 Correct 83 ms 9208 KB Output is correct
6 Partially correct 35 ms 9208 KB Output is partially correct
7 Partially correct 47 ms 9208 KB Output is partially correct
8 Partially correct 272 ms 9244 KB Output is partially correct
9 Partially correct 272 ms 9332 KB Output is partially correct
10 Partially correct 1289 ms 9244 KB Output is partially correct
11 Execution timed out 1569 ms 9208 KB Time limit exceeded
12 Halted 0 ms 0 KB -