oj.uz

답안 #130345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130345 2019-07-14T21:37:19 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 = (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 = 1; i - a >= 0 && j + a <= t.size(); a++) {
			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)){
				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;
			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:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int a = 1; i - a >= 0 && j + a <= t.size(); a++) {
                                ~~~~~~^~~~~~~~~~~
necklace.cpp:72:24: 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:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:103:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++) {
                 ~~^~~~~~~~~~
necklace.cpp:122: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 17 ms 9208 KB Output is partially correct
2 Partially correct 19 ms 9336 KB Output is partially correct
3 Partially correct 24 ms 9208 KB Output is partially correct
4 Partially correct 30 ms 9208 KB Output is partially correct
5 Partially correct 101 ms 9208 KB Output is partially correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 17 ms 9208 KB Output is partially correct
2 Partially correct 19 ms 9336 KB Output is partially correct
3 Partially correct 24 ms 9208 KB Output is partially correct
4 Partially correct 30 ms 9208 KB Output is partially correct
5 Partially correct 101 ms 9208 KB Output is partially correct
6 Partially correct 125 ms 9208 KB Output is partially correct
7 Partially correct 139 ms 9208 KB Output is partially correct
8 Partially correct 345 ms 9208 KB Output is partially correct
9 Partially correct 405 ms 9336 KB Output is partially correct
10 Partially correct 1341 ms 9336 KB Output is partially correct
11 Execution timed out 1583 ms 9212 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 17 ms 9208 KB Output is partially correct
2 Partially correct 19 ms 9336 KB Output is partially correct
3 Partially correct 24 ms 9208 KB Output is partially correct
4 Partially correct 30 ms 9208 KB Output is partially correct
5 Partially correct 101 ms 9208 KB Output is partially correct
6 Partially correct 125 ms 9208 KB Output is partially correct
7 Partially correct 139 ms 9208 KB Output is partially correct
8 Partially correct 345 ms 9208 KB Output is partially correct
9 Partially correct 405 ms 9336 KB Output is partially correct
10 Partially correct 1341 ms 9336 KB Output is partially correct
11 Execution timed out 1583 ms 9212 KB Time limit exceeded
12 Halted 0 ms 0 KB -