oj.uz

Submission #133109

# Submission time Handle Problem Language Result Execution time Memory
133109 2019-07-20T07:37:32 Z E869120 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 35832 KB 
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

const long long mod = 2147483647;

int N, M, pa[3009][3009]; long long as[3009], at[3009], power[3009];
int EA[6009], EB[6009];

long long hash_s(int l, int r) {
	// [l, r]
	return (as[r + 1] - as[l] * power[r - l + 1] + mod * mod) % mod;
}

long long hash_t(int l, int r) {
	// [l, r]
	return (at[r + 1] - at[l] * power[r - l + 1] + mod * mod) % mod;
}

int get_pb(int l, int r) {
	int len = 0;
	for (int i = 11; i >= 0; i--) {
		int cx = len + (1 << i);
		if (!(l + cx - 1 < N && r + cx - 1 < M)) continue;
		long long v1 = hash_s(l, l + cx - 1);
		long long v2 = hash_t(r, r + cx - 1);
		if (v1 == v2) len = cx;
	}
	return len;
}

tuple<int, int, int> solve(string S, string T) {
	for (int i = 0; i <= 3000; i++) { as[i] = 0; at[i] = 0; power[i] = 0; }
	for (int i = 0; i < S.size(); i++) {
		as[i + 1] = as[i] * 101LL;
		as[i + 1] += (S[i] - 'a' + 1);
		as[i + 1] %= mod;
	}
	for (int i = 0; i < T.size(); i++) {
		at[i + 1] += at[i] * 101LL;
		at[i + 1] += (T[i] - 'a' + 1);
		at[i + 1] %= mod;
	}
	power[0] = 1; for (int i = 1; i <= 3000; i++) power[i] = (101LL * power[i - 1] % mod);

	N = S.size(); M = T.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			pa[i][j] = 0;
			if (S[i] == T[j]) pa[i][j] = 1;
			if (i >= 1 && j >= 1 && S[i] == T[j]) {
				pa[i][j] = pa[i - 1][j - 1] + 1;
			}
		}
	}

	int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
	for (int i = 0; i <= N; i++) {
		// S における境界が i の場合
		vector<int> A, B;
		for (int j = 0; j < M; j++) {
			if (i == N) A.push_back(0);
			else A.push_back(get_pb(i, j));
		}
		for (int j = 0; j < M; j++) {
			if (i == 0) B.push_back(0);
			else B.push_back(pa[i - 1][j]);
		}
		for (int j = 0; j <= 6000; j++) { EA[j] = (1 << 29); EB[j] = -(1 << 29); }
		for (int j = 0; j < N; j++) {
			EA[A[j] + j] = min(EA[A[j] + j], j);
			EB[max(0, -B[j] + j + 1)] = max(EB[max(0, -B[j] + j + 1)], j);
		}
		
		// ret1 には条件を満たす最も左のインデックスを記録
		int ret1 = -(1 << 29);
		for (int j = 0; j <= 6000; j++) {
			ret1 = max(ret1, EB[j]);
			int cr = ret1, cl = EA[j];
			if (maxn < cr - cl + 1) {
				maxn = cr - cl + 1;
				maxid = make_pair(i - B[cr], cl);
			}
		}
	}
	return make_tuple(maxn, maxid.first, maxid.second);
}

int main() {
	string A1, B1, B2; cin >> A1 >> B1; B2 = B1; reverse(B2.begin(), B2.end());
	tuple<int, int, int> v1 = solve(A1, B1);
	tuple<int, int, int> v2 = solve(A1, B2);

	cout << max(get<0>(v1), get<0>(v2)) << endl;
	if (get<0>(v1) > get<0>(v2)) cout << get<1>(v1) << " " << get<2>(v1) << endl;
	if (get<0>(v1) <= get<0>(v2)) cout << get<1>(v2) << " " << M - (get<2>(v2) + get<0>(v2)) << endl;
	return 0;
}

Compilation message

necklace.cpp: In function 'std::tuple<int, int, int> solve(std::__cxx11::string, std::__cxx11::string)':
necklace.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
necklace.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 892 KB Output is correct
2 Correct 7 ms 892 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 892 KB Output is correct
2 Correct 7 ms 892 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 50 ms 2680 KB Output is correct
7 Correct 51 ms 2680 KB Output is correct
8 Correct 46 ms 2552 KB Output is correct
9 Correct 49 ms 2552 KB Output is correct
10 Correct 51 ms 2680 KB Output is correct
11 Correct 51 ms 2720 KB Output is correct
12 Correct 48 ms 2552 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 892 KB Output is correct
2 Correct 7 ms 892 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 50 ms 2680 KB Output is correct
7 Correct 51 ms 2680 KB Output is correct
8 Correct 46 ms 2552 KB Output is correct
9 Correct 49 ms 2552 KB Output is correct
10 Correct 51 ms 2680 KB Output is correct
11 Correct 51 ms 2720 KB Output is correct
12 Correct 48 ms 2552 KB Output is correct
13 Execution timed out 1570 ms 35832 KB Time limit exceeded
14 Halted 0 ms 0 KB -